| Autor |
Beitrag |
    
sabine Dietrich
| | Veröffentlicht am Freitag, den 12. Januar, 2001 - 09:22: | 
|
Zu einem ungerichtetem Graphen G= (E,K) ist der Kantengraph L(G)=(E index L(G), K index L(G)) definiert durch E index L(G):=K und
K index L(G):={{ki,kj}I ki und kj sind inzidente Kanten von G}.
a) Zeige: G ist Eulergraph => L(G) ist Eulergraph
b) Beweise oder widerlege die Umkehrung von a)
c) Zeichne L(G) für G=K3, K4, K2,2 , K2,3 und K3,3
(3,4 , 3,3 usw sind Indexe...) |
Matroid (Matroid)
| | Veröffentlicht am Freitag, den 12. Januar, 2001 - 16:53: |
|
Ein Eulergraph ist ein zusammenhängender Graph, in dem eine Euler-Tour existiert. Das ist eine Tour ohne Kantenwiederholung, in der jede Kante genau einmal vorkommt.
Es gibt einen Satz, der sagt: G ist eulersch <=> Alle Ecken haben gerade Valenz (=: Anzahl mit der Ecke inzidenter Kanten).
Wenn also G Eulergraph ist, dann sind mit jeder Ecke gerade viele Kanten inzident. In L(G) werden die Kanten zu Ecken und zwei Ecken in L(G) sind durch eine Kante verbunden, wenn diese beiden Ecken in G eine gemeinsame Ecke haben.
Betrachte eine Kante e aus G. Diese ist mit 2 Ecken inzident. Jede der beidn Ecken hat gerade Valenz, sagen wir v1 und v2. Die Ecke e ist also in G mit v1-1 + v2-1 = gerade vielen anderen Kanten über eine ihrer Ecken inzident. In L(G) ist also auch die Valenz jeder Ecke gerade.
b) Gegenbeispiel: Sei E={a,b,c,d}und von a zu jeder anderen Ecke gebe es eine Kante (also ein Dreibein). L(G) ist dann ein Kreis. Kreise sind eulersch, aber G eben nicht.
Gruß
Matroid |
|
