Euler grafikonok

Simonenko EA Diszkrét matematika. előadások

Euler ciklus egy ciklus, amely átmegy mindkét peremén a grafikon pontosan egyszer. Ennek megfelelően a gráf tartalmaz ciklus, az úgynevezett Euler. Fogalmazza kritérium Euler grafikon:

Tétel (Euler, 1736.). Connected irányítatlan gráf tartalmaz Euler-ciklus akkor és csak akkor, ha páratlan számú csúcsok foka nulla.

Egy irányított gráf készítményt a tétel némileg eltérő: egy irányított gráf egy Euler ciklust, ha, és csak akkor, ha csatlakoztatva van, és a minden csúcsa egyenlő a bemeneti szintje a kimenet.

Ha Euler ciklus a grafikonon létezik, az azt jelenti, hogy a következő mentén ez a ciklus, akkor lehet, hogy dolgozzon egy grafikont a papíron felemelése nélkül ceruza tőle.

Tegyük fel, hogy kapnak egy irányítatlan G gráf kielégíti Euler-tétel. Tekintsük megállapító algoritmust Euler ciklusban a grafikonon. Ez az algoritmus alapján bejárja a grafikonon mélységben. Az átmenet a következő felső eltávolítja a megfelelő megtett borda. Miután érzékelte csúcsok, amelyek a bordák nem megy (már őket távolítani kora áthaladó mély), rögzíti a szám a verem. csúcsok detektálás nulla élek azt sugallja, hogy talált egy ciklust. Meg lehet szüntetni, és a paritás vertex fok nem fog változni. A folyamat addig tart, amíg nincs áthaladni élek. Miután vége az egész gráf bejárása mélységben csúcsok számát kell tárolni egy köteg nagyságrendű Euler ciklust.

Bejelentkezés. Count Graph, képviseli szomszédsági mátrixba; a verem tetején Stack Euler ciklusszám kiindulási csúcsból U.

Minden gráf csúcsainak V Graph, a szomszédos U: Graph [U, V]: = 0, Graph [V, U]: = 0; DFS (Graph, Stack, V).

A feladat megtalálni Hamilton-kör szorosan kapcsolódik a probléma az utazó ügynök (a házaló). Fogalmazott így: létezik n városokban, köztük lévő távolságot ismertek. Merchant felkeresi az összes n városok pontosan egyszer visszatérve az egyik a megkezdett útját. Szükséges, hogy megtaláljuk a módját, az utazó ügynök minimális teljes hossza.

3. ábra: Példa tetagrafa

Simonenko EA Diszkrét matematika. előadások

síkgráfok

Azt mondják, hogy a grafikon kerül bármilyen felületen, ha lehet levonni ezen a felületen keresztezése nélkül élek. Ha a gráf lehet helyezni a gépet, egy grafikon az úgynevezett sík. Gróf meghatározott sík felületen nevezett.

Által határolt területen élei egy sík gráf, és nem tartalmaznak más csúcsok és az élek a grafikon, az úgynevezett egy arc. A külső része a sík tekintetében a grafikonon is tekinthető egy arc. A szám a lapos arcához G jelöli R (G).

Tétel (Euler-képlet). Egy csatlakoztatott sík gráf G = (V E) egyenlőség n - m + r = 2, ahol n = V. m = E és R = R (G).

Ha a G - csatlakoztatott sík gráf, n> 3. 3, akkor m n - 6. Valóban, minden arc által határolt, legalább három él, és az egyes lábak korlátok nem több, mint két oldal tehát R3 2 m. Ebből és a Euler formula: = 2 n - m + r n - m + 2 m / 3. Következő: 3 n - 3 m + 2 m 6 m 3 n - 6.

Megmutatjuk, hogy K 5 és K 3,3 nem sík. A grafikon K 5 mi n = 5 és m = 5, 4/2 = 10. Behelyettesítve n és m az egyenlőtlenség 10 március 05-10 június 9 Ez az ellentmondás grafikon K 5 nem lehet sík.

4. ábra: A grafikonok K5 és K3,3

A grafikon K 3,3 van n = m = 6 és 9. Ebben grafikonon nem „háromszögek”, így amikor szóló, a sík minden egyes arc határolja legalább négy szélén, és így 4 r 2 r m m 2. Szerint a Euler-képlet: 6-9 + r = r 2 r = 5. behelyettesítve egyenlőtlenséget: 5 február 10 szeptember 9 ellentmondás.

Planar grafikont, amelyben minden részletét, beleértve a külföldi, háromszögek, az úgynevezett

planáris háromszögelési. Maximális lapos grafikon egy olyan grafikon, amely megszűnik, hogy sík azzal a kiegészítéssel, minden él.

Tétel. Gróf Gróf maximális sík akkor és csak akkor, ha sík háromszögelés.

Minden legnagyobb síkbeli gráf, a egyenlőség m = 3, n - 6.

Fedjük le és függetlenség

Azt mondják, hogy a csúcsa a grafikon kiterjed az esetet a bordái, és egy él esetet fedi a tetején. Ez két problémát vet fel: 1) keresni a minimális csúcsok száma, amely az összes szélei a G gráf (bevonat vertex száma 0 α (G)); 2) található a élek minimális száma, amely az összes csúcsainak G (száma parti bevonat

A teljes gráf K n:

α 0 (K n) = n - 1. α 1 (K n) = [N 2]. (Ahol a [] jelöli a "plafon".)

A csúcsok halmaza egy G gráf nevezzük független. ha nincs két csúcsot a készlet nem szomszédosak. A legnagyobb csúcsok száma a független halmazt nevezzük

vertex függetlenség száma β 0 (G). és ennek megfelelően több, a legnagyobb. A készlet nem szomszédos élei egy G gráf nevezzük független. A legnagyobb számú élek a független halmaza vonal hívott szám függetlenségét β 1 (G).

A teljes gráf K n:

α 0 (K n) = n - 1. β 1 (K n) = [N 2]. (Ahol a [] jelöli a "padlón".)

Tétel. Bármely gráf nélküli izolált csúcsok egyenletet:

a0 + β 0 = n = a 1 + β 1.