Graphentheorie

Aufrufe: 126     Aktiv: 31.07.2022 um 21:11

0
Aufgabe: 

Es sei $E$ eine Menge von 200 olympischen Athleten und $K=\{\{a,b\} | a,b \in E, a≠b, a,b \enspace haben \enspace dieselbe \enspace Anzahl \enspace an \enspace Medaillen\}$.

Angenommen, es werden 200 Medaillen an die Athleten aus $E$ verliehen. Es sei $G=\{E,K\}$ der Graph mit Eckenmenge $E$ und Kantenmenge $K$. 
 
(a) Ist $G$ planar?
(b) Ist $G$ eulersch, falls $G$ zusammenhängend ist?

Lösung

Fall 1: 
Falls diese 200 Medaillen gleich auf alle Athleten verteilt wird, ist $G$ der vollständige Graph $K_{200}$ und nicht planar. Es gilt ja, dass wenn $G$ planar ist $k≤3e-6$, wobei $k$ die Kantenanzahl und $e$ die Eckenanzahl ist. Das heißt, ich kann die Umkehrung dieser Implikation nutzen: Gilt nicht $k≤3e-6$, so ist $G$ nicht planar. 


$\Rightarrow$ ${200 \choose 2} ≤3*200-6$ gilt offensichtlich nicht und deshalb ist $G$ nicht planar. 

Eulersch ist er auch nicht, da alle Ecken Grad $199$ haben, was nicht gerade ist. 


Was mache ich aber in Fall 2: Die 200 Medaillen werden nicht gleich auf die Athleten verteilt?

EDIT vom 29.07.2022 um 20:10:

Würde mich echt freuen, falls jemand rüberschauen kann :)
Diese Frage melden
gefragt

Punkte: 22

 

Ja, ich hab drüber geschaut, was ausprobiert, aber ohne Erfolg. Vermutlich bin ich auch nicht der einzige.   ─   mikn 29.07.2022 um 21:33

Hmm, trotzdem danke!   ─   huhu123 29.07.2022 um 23:14
Kommentar schreiben
1 Antwort
0
Habe auch mal drübergeguckt.

Zu a) Ich würde den Implikationspfeil da weg lassen (woraus folgt denn da was?) und vielleicht die Zahlen noch ausrechnen. Das ist aber eher Optik, insgesamt aus meiner Sicht ein richtiger Ansatz.

Dann würde ich mir den anderen Extremfall anschauen: Was passiert, wenn einer alle Medallien bekommt?

Zu b) Hier würde ich vermutlich noch den Satz zitieren, auf den Du Dich beziehst - hast Du in a) ja schön gemacht.

Danach: Warum ist hier der von Dir betrachtete Fall der einzige, der betrachtet werden muss?
Diese Antwort melden
geantwortet

Punkte: 2.17K

 

Danke für deine Antwort!   ─   huhu123 31.07.2022 um 13:04

1
Du kannst die Antwort akzeptieren (Haken links anklicken), wenn für Dich die Frage geklärt ist, und/oder upvoten (grauer Pfeil), wenn Du mit der Antwort zufrieden warst. Das markiert zum einen Deine Frage als "erledigt" und zum anderen kriegt man als Antwortender auch ein paar Gummipunkte.   ─   joergwausw 31.07.2022 um 21:11

Kommentar schreiben