Aussagen zu Graphen?

25.02.2013, 19:49

fbausc

Aussagen zu Graphen?

Hallo,

ich habe folgende Fragestellungen, die ich mit wahr oder falsch + Begründung angeben soll:

Bei den folgenden Aussagen bin ich mir nicht ganz sicher, bzw. weiß auch nicht wie ich das begründen soll!

"Jeder Graph, der höchstens zwei Kreise enthält ist planar"
?

"Gibt es einen planaren Graphen mit 7 Knoten und 22 Kanten"
?

"Es gibt einen bipartiten Graphen mit 10 Knoten und 26 Kanten."
?

"Es gibt einen 3-regulären Graphen mit 17 Knoten."
Nein, da n(g)*degC(v)/2 = (17*3)/2 = 25,5 ist d.h. keine ganze Kanteanzahl vorhanden????

"Es gibt einen 3-regulären Graphen mit 17 Kanten."
?

"Der Kantengraph eines Baumes ist ein Baum."
Nein, da der Kantengraph eines baumes mit 4 Knoten einen Kreis besitzt?

Danke für eure Hilfe!

28.02.2013, 02:16

Karamuto

Auf diesen Beitrag antworten »

Habe da mal ein wenig durchgerechnet und kann dir nun folgende tipps geben:

1. Überlege einfach mal was für die Fälle kreisfrei u. 1-2 Kreise gilt, wie sieht der Graph dann aus?

2. Ihr habt sicher Sätze oder Lemma über planare Graphen gehabt.

3. Nach meinem wissen ex. kein solcher ich weiß nur gerade nicht warum

4. Richtig argumentiert

5. Nutze gleiches Argument wie in 4

6. Es wird klarer wenn man sich überlegt das ein Baum mit n Knote n-1 Kanten hat, aber ja es ist falsch

28.02.2013, 10:21

RavenOnJ

Auf diesen Beitrag antworten »

RE: Aussagen zu Graphen?

Zitat:

Original von fbausc

"Es gibt einen bipartiten Graphen mit 10 Knoten und 26 Kanten."

Diese Aussage ist falsch. Du kannst dir das überlegen, indem du der Kantenzahl eines vollständigen Graphen die eines bipartiten Graphen (beide jeweils mit 10 Knoten) gegenüberstellst. Da du die Knoten eines bipartiten Graphen so in zwei Gruppen partionieren kannst, dass zwischen den Knoten innerhalb einer Gruppe keine Kanten existieren, kannst du eine einfache Beziehung für die maximal mögliche Zahl von Kanten eines bipartiten Graphen aufstellen: $\begin{eqnarray*} E_{max}(k,m)\Big\rvert_{k+m=10}\ge 26 \end{eqnarray*}$ , wobei $\begin{eqnarray*} k,m \end{eqnarray*}$ die Zahl der Knoten in den jeweiligen Partitionen ist. Diese Ungleichung kann für kein Paar $\begin{eqnarray*} k,m \end{eqnarray*}$ erfüllt sein.

28.02.2013, 15:53

fbausc

Auf diesen Beitrag antworten »

Ich vestehe nur halb. Ich hab mir das jetzt so überlegt!
Wenn ich ein bipartiten Graphen mit 10 Knoten in 2 Partitionen mit gleich vielen Knoten teile, erhalte ich Emax für den Graphen richtig? 5*5 = 25. Wenn ich die Knotenanzahl in beiden Partitionen vertausche z.B. 6*4 oder 7*3 wird die Kantenanzahl ja kleiner als 25. Somit kann es nicht mehr Kanten als 25 geben!

Das mit der Ungleichung hab ich allerdings nicht ganz verstanden!

28.02.2013, 18:17

RavenOnJ

Auf diesen Beitrag antworten »

Man kann eine Formel aufstellen für die Zahl der Kanten eines vollständigen Graphen, das ist $\begin{eqnarray*} \frac{N(N-1)}2 \end{eqnarray*}$ mit der Zahl der Knoten $\begin{eqnarray*} N \end{eqnarray*}$ . In einem bipartiten Graphen gibt es $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} m = N-k \end{eqnarray*}$ Knoten, die untereinander keine Kanten aufweisen. In einem bipartiten Graphen fehlen also für die Vollständigkeit mindestens

$\begin{eqnarray*} \frac{k(k-1)}2 \end{eqnarray*}$

Kanten aus der einen Partition und

$\begin{eqnarray*} \frac{m(m-1)} 2 = \frac{(N-k)(N-k-1)}2 \end{eqnarray*}$

Kanten aus der anderen Partition. Die maximale Kantenzahl in diesem bipartiten Graphen ist also

$\begin{eqnarray*} \frac{N(N-1)} 2 -\frac{k(k-1)} 2 - \frac{(N-k)(N-k-1)}2 = k(N-k) =km =: E_{max}(k,m)\Big|_{k+m=N} \end{eqnarray*}$

In deinem Fall müsste also gelten:

$\begin{eqnarray*} E_{max}(k,m)\Big|_{k+m=10} = k(10-k)\ge 26 \end{eqnarray*}$ ,

was offensichtlich nicht möglich ist, da das Maximum dieser Funktion bei k=m=5 liegt mit
$\begin{eqnarray*} E_{max}(5,5) = 25 \end{eqnarray*}$ .

03.03.2013, 16:09

fbausc

Auf diesen Beitrag antworten »

Okay. Vielen dank.
Noch ein paar Ideen zu den anderen Aufgaben?

Neue Frage »

Antworten »

Aussagen zu Graphen?

Verwandte Themen