Euler grafikonok - studopediya

Meghatározás 1.Eylerovym egy grafikon úgynevezett utat tartalmazó minden éle a grafikon és áthalad az egyes egyszer.

1. példa Tekintsük a gráf

Meghatározása 2.Eylerovym ciklus Egy gráf egy ciklus, amely tartalmazza az összes szélei a grafikonon, és áthaladó mindegyik egyszer.

Meghatározása 3.Graf amelynek Euler ciklus, az úgynevezett Euler gráf.

2. példa Tekintsük a gráf

1. Tétel Euler gráf összefüggő, és minden csúcs még.

Kapcsolódás a meghatározása az Euler gráf. Euler ciklus tartalmaz minden él, és csak egy alkalommal. Következésképpen a minden csúcsa a grafikon áll két egyenlő részből áll: a bemenetek számát a csúcspont és a kimenetek számát a csúcs.

Tétel 2. Ha a G gráf (x, t) csatlakoztatott és annak minden csúcsai is, azt Euler-ciklust.

3. tétel Ha a gráf G (x, t) van Euler végei által az A és B, majd a G gráf (X, T) és a kapcsolódó A és az annak csak páratlan csúcsokat.

Ha az útvonal kezdődik és végződik egy B. akkor az A és páratlan csúcsot, akkor is, ha az út többször áthalad őket. A tetején minden más utat kell vezetni, és visszavonja tőle, azaz a még a többi csúcsot.

Tétel 4. Ha a G gráf (X, T) és a kapcsolódó A és az annak csak páratlan csúcsai, a gráfnak Euler végei által az A és B.

Tétel 5. Ha a G gráf (X, T) van csatlakoztatva, akkor lehetséges egy gyűrűs útvonalat tartalmazó valamennyi élét pontosan két alkalommal, minden irányban egyszer.