Graphentheorie - unmöglicher Graph

Aufrufe: 664     Aktiv: 17.06.2020 um 11:53
0

Hallo! Ich habe einen gerichteten Graph mit folgender Gradtabelle:

 

 

deg+ = die ausgehenden Kanten

deg- = die eingehenden Kanten

 

Ich soll zeigen, dass so ein Graph nicht möglich sei. Auf jeden Fall ist die Summe deg+ = 40 und Summe deg- = 42

Irgendwas sagt mir das geht nicht, dass mehr Kanten eingehend sind. Aber ich finde dazu kein Lemma oder sonstiges! Wie kann ich das begründen?

 

Vielen Dank!

Diese Frage melden
gefragt

Student, Punkte: 27

 
Kommentar schreiben
1 Antwort
1

Dazu hab ich eine Frage:

Sind doppelte Kanten erlaubt? (Sprich, du hast zB 2 Kanten zwischen v1 und v3).
Wenn ja, funktioniert das sowieso, egal wieviel du von was hast.


Wenn nicht:
bei v3 sollen 8 Kanten eingehen - Sprich von jedem anderen Knoten jeweils eine (weil es ja 9 knoten gibt und man in der regel keine kante zum eigenen knoten haben sollte).
Da jedoch von v2 keine Kante weggehen darf, ist alleine an dem Punkt schon gezeigt, wieso das niemals funktionieren kann

Diese Antwort melden
geantwortet

Student, Punkte: 1.12K

 
Also mit doppelte Kanten haben wir noch nie etwas gemacht, deshalb gehe ich davon aus, dass es nicht geht.

Stimmt! Das habe ich noch gar nicht gesehen. Würde das quasi als Beweis schon reichen?
   ─   lisa711 17.06.2020 um 10:37
Ich glaube das hängt in dem Fall dann immer von der Formulierung und der (ich sag mal) korrekten Aufschreibweise ab, sollte theoretisch aber für einen Beweis ausreichen.

Bei der Aufgabe geht es ja nicht um einen allgemeinen Beweis, sondern quasi um die Widerlegung, dass dieser Graph so möglich ist
   ─   julianb 17.06.2020 um 11:24
Das stimmt! Ich denke vorallem mit einer Skizze denke ich sollte es ausreichen :) Vielen lieben Dank!   ─   lisa711 17.06.2020 um 11:53

Kommentar schreiben