Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl maximaler Kanten eines Graphen bestimmen

Anzahl maximaler Kanten eines Graphen bestimmen

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

frage344 aktiv_icon

16:41 Uhr, 15.12.2022

Hey, ich bräuchte ein paar Tipps wie ich diese Aufgabe lösen kann. Mir gehen die Ideen aus....
Also ich weiß , dass Jeder Graph eine gerade Anzahl von Knoten mit ungeradem Grad hat. Zudem weiß ich, dass für Anzahl Kanten gilt:

\sum_{v \in V}^{}

deg(v) = 2 |E|
wobei V die Menge der Knoten ist und E die Menge der Kanten.
Ich hatte diese Gleichung nach |E| umgestellt . Nun muss ich es hinbekommen , dass

\sum_{v \in V}^{}

deg(v) maximal wird.
Aber dieses "mindestens" lässt mich auf keine Idee kommen irgendwie ...
Hoffe es findet sich Hilfe
Gruß

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Kartoffelfan aktiv_icon

20:59 Uhr, 15.12.2022

Ansatz "maximales Maximum",

also für ungerades

n \geq 7

genau

⌈ \frac{n}{2} ⌉ = \frac{n + 1}{2}

Knoten Grad 3 und genau

⌊ \frac{n}{2} ⌋ = \frac{n - 1}{2}

Knoten Grad 5.

Gibt

\frac{\frac{n + 1}{2} \cdot 3 + \frac{n - 1}{2} \cdot 5}{2}

Kanten, sofern möglich.

Durchrechnen:

\frac{\frac{n + 1}{2} \cdot 3 + \frac{n - 1}{2} \cdot 5}{2} = \frac{n \cdot 8 - 2}{4} = \frac{4 \cdot (2 \cdot n - \frac{1}{2})}{4} = 2 \cdot n - \frac{1}{2},

also geht das nicht.

Wir tauschen einen Knoten Grad 5 gegen einen Knoten Grad 4 und testen:

\frac{\frac{n + 1}{2} \cdot 3 + \frac{n - 3}{2} \cdot 5 + 4}{2} = \frac{8 \cdot n - 4}{4} = \frac{4 \cdot (2 \cdot n - 1)}{4} = 2 \cdot n - 1,

Bingo !

Für

⌈ \frac{n}{2} ⌉ = \frac{n + 1}{2}

Knoten Grad

3,

einen Knoten Grad 4

und

⌊ \frac{n}{2} ⌋ - 1 = \frac{n - 3}{2}

Knoten Grad 5

ergibt sich die maximale Anzahl von

2 \cdot n - 1

Kanten.

Für

n = 7

habe ich mal einen entsprechenden 13-kantigen Graphen gemalt, siehe Anhang.

frage344 aktiv_icon

13:57 Uhr, 18.12.2022

Hi, erstmal vielen Dank für die Antwort. Ich konnte deinem Beweis soweit folgen, aber warum musste man dann den einen Knoten austauschen mit einem Grad 4 Knoten?
Gruß

Kartoffelfan aktiv_icon

17:49 Uhr, 18.12.2022

Die Anzahl der Kanten muss eine natürliche Zahl sein.

Und

"...aber warum musste man dann den einen Knoten austauschen mit einem Grad 4 Knoten?"

ist Affendeutsch und lässt mich gruseln, sodenn ich bezweifle,
dass Du irgendetwas verstanden hast wie auch, dass Kommunikation
mit Dir überhaupt Sinn macht.

Bitte sichte Theorie zum Thema,

z . B

. ca.

20

Seiten dort:

home.mathematik.uni-freiburg.de/junker/skripte/DAS-SS10.pdf

Und bitte denk mal ein wenig nach, bevor Du fragst.

Ich bin raus.

Und Tschüss !

Punov aktiv_icon

19:35 Uhr, 18.12.2022

Hallo, Kartoffelfan!

Bitte zügele deine Zunge! Dieser Ton ist hier vollkommen unangemessen!

(1) Es wurde in der Frage ausdrücklich Folgendes ausgewählt: "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." Du hast allerdings eine Komplettlösung geliefert. Darum sind inhaltliche Nachfragen jeder Art vollkommen berechtigt und zu akzeptieren! Wenn es dich ärgert, dass deine Komplettlösung nicht hinreichend gewürdigt zu werden scheint, dann gib' keine Komplettlösung.

(2) Deine Antwort wurde dankend entgegengenommen. Wieso reagierst du auf Höflichkeit derart unhöflich?

(3) Egal, was die ersten beiden Punkte beinhalten: Ein derart diffamierender Ton ist niemals (!) gerechtfertigt. Dies ist ein freiwilliges (!) Hilfeforum, wenn du Nachfragen nicht verarbeiten magst, dann antworte schlichtweg nicht. Ich erinnere an das Motto dieses Forums: "Doofe Fragen in Mathe gibt's nicht!"

Viele Grüße

Kartoffelfan aktiv_icon

20:07 Uhr, 18.12.2022

Du verdrehst die Dinge, Punov,
und das kannst Du Dir sparen.
Und dieses Motto sei doch mal stark
zu überdenken...

Punov aktiv_icon

20:10 Uhr, 18.12.2022

Ich denke an "Affendeutsch" und generellem Zweifel an der Kommunikation gibt es nicht viel zu drehen oder zu deuten. Und das Motto ist so, wie es ist. Da muss man sich halt überlegen, ob man passt oder nicht.

Kartoffelfan aktiv_icon

20:33 Uhr, 18.12.2022

Ach so, und Du musst dann hier den Moralapostel geben
und mich instruieren, wie ich denn zu kommunizieren habe ?
Ich sag Dir mal was: Du hast mir gar nichts zu sagen !
Ja, und Vorschlag an Dich: Übernimm Du doch diesen Thread
und stehe dem Fragesteller mit seinen äusserst stringent
und dezidiert formulierten Fragen Rede und Antwort.

Matheboss aktiv_icon

07:42 Uhr, 19.12.2022

Kartoffelfan ist hier schon mit anderen Namen aufgetaucht,

z . B

. Kartoffelchipsman.

Ich werde Kartoffelfan auch wieder dem Admin zum Löschen vorschlagen.

@"Kartoffeltroll"
Das Motto dieses Forums heißt;

"Es gibt keine doofen Fragen..."

Du bist nicht gezwungen die Fragen zu beantworten!

frage344 aktiv_icon

16:39 Uhr, 19.12.2022

Also, erstmal zieh ich mein Danke wieder zurück. Auf so eine Hilfe kann ich verzichten. Wer hat dich denn gebissen? Ich hatte gefragt, was du mit der Zeile " es wird ein Knoten grad 5 mit einem Grad 4 getauscht" meinst. Wenn du schon eine Komplettlösung schickst (was nicht schlimm ist) , dann geh doch bitte sachlich auf meine Frage ein, da ich deine Aussage an der Stelle nicht verstanden hatte. Was sich manche Menschen einbilden, unglaublich.

1565000

1564877

	Status: nicht eingeloggt	Noch nicht registriert?