Euleri grafikon

A gráfelméletben egy euleri út vagy euleri út , vagy akár egy irányítatlan gráf euleri lánca olyan út, amely minden élen áthalad, élenként egyszer. A nevet Leonhard Eulerre hivatkozva adták . Ha egy ilyen út visszatér a kiindulási ponthoz, akkor euleri pályáról vagy euleri ciklusról , vagy akár euleri túráról beszélünk . Az a gráf, amely egy euleri kört beismer , állítólag euleri . Ha beismer egy euleri tanfolyamot , akkor azt félig euleriánusnak mondják .

Példák

Boríték tervezési probléma

Az euleri út fogalmát a boríték kialakításának problémája szemlélteti. Kérdés boríték megrajzolása a ceruza felemelése nélkül és anélkül, hogy ugyanazt a vonalat többször megrajzolnánk. Az alábbi grafikon segítségével modellezhetjük a rajzot. Az euleri út megfelel annak, ha egy grafikont rajzolunk egy lapra, anélkül, hogy fel kellene emelni a ceruzát.

• Példa egy euleri útvonalat befogadó gráfra.

• Kézi rajz ceruza felemelése nélkül

A hét Königsberg-híd problémája

A probléma a hét Königsberg híd a probléma az, hogy az egyik lehet átkelni minden híd, a város Königsberg egy séta, ha minden hidat. Amint az az alábbi ábrán látható, a problémát egy grafikon segítségével modellezik az alábbiak szerint: a hidak alkotják a gerinceket, a szigetek és a bankok a csúcsokat. Mivel ez a grafikon nem ismeri el az euleri utat, a problémának nincs megoldása.

→ →

Oktaéder grafikonja

Megfontolhatjuk egy poliéder , például egy oktaéder grafikonját is . A sokszög csúcsai és élei a gráf csúcsai és élei.

Euler tétele

Egy csúcs mértéke

A diploma egy csúcs az élek számát érkezik a csúcsba (incidens élek). A következő grafikonokban megadjuk az egyes csúcsok fokozatait.

• A 7 Königsberg-híd grafikonja és egy másik grafikon az 5 kamráról szól. Ezek a grafikonok nem ismerik el az euleri utakat. A feltüntetett számok fokok.

• 1. és 4. Grafikonok, amelyeknek van egy euleri útja, de nincs euleri körük. 2. Grafikon megoldás nélkül. 3. Euler-kört tartalmazó grafikon.

A tétel állítása

Euler-tétel, más néven Euler-Hierholzer-tétel, kétféle jellemzéssel rendelkezik:

• Egy összekapcsolt gráf akkor és csak akkor enged be egy euleri utat, ha annak csúcsai páros fokúak, legfeljebb kettő kivételével.
• Egy összekapcsolt gráf csak akkor engedi be az euleri kört, ha minden csúcsa egyenletes fokú.

Demonstráció

Euler 1736-ban bemutatta a szükséges feltételeket. Az alábbi teljes bizonyítékot Carl Hierholzer német matematikus tette közzé 1873-ban. Euler-nek néha az egyenértékűséget tulajdonítják, mint Diestel gráfelméleti könyvében (lásd Th. 1.8.1.). A két közvetlen irányt a következőképpen mutatjuk be.

Tegyük fel, hogy van euleri út, és haladjon úgy, hogy eltávolítja a felhasznált éleket. A csúcs minden egyes szakaszánál (kivéve az elején és a végén) a csúcsra érkező hegygerincet és az onnan távozó gerincet törlik. Így a kezdő vagy a cél csúcs kivételével a fok paritása változatlan marad. Az útvonal végén az összes él eltávolításra kerül, ami lehetővé teszi a csúcsok paritásán való következtetést.

A közvetett, azaz a reciprok jelentéseket az alábbiak szerint lehet bemutatni.

Mutassuk meg, ha az összes csúcs egyenletes fokú. Kezdjük a grafikon bármely s 0 csúcsán . Kölcsönözzünk éleket, távolítsuk el őket a grafikonról, ameddig csak lehetséges. Mivel a fokok párosak, szükségszerűen visszatértünk az s 0 csúcshoz, és találtunk egy s 0 - s 1 - ... - s 0 áramkört . Ha nincs több él, akkor van egy Euler-áramkörünk. Ellenkező esetben újrakezdjük a folyamatot annak érdekében, hogy egy másik áramkört ki lehessen mutatni, egy s i csúcsból , amelyből egy él indul. Ezután kapunk egy másik s i - ... - s i áramkört , amelyet az előző áramkörbe épp beillesztettünk s i helyére  :

s 0 - s 1 - ... - s i - ... - s i - s i + 1 - ... s 0 .

Addig ismételjük a folyamatot, amíg az összes élt ki nem használtuk, és nem kapunk egy Euler-kört.

Algoritmusok

Hierholzer algoritmus

Valójában írhatunk egy számítógépes programot egy Euler-útvonal vagy áramkör kiszámításához, ha van ilyen. Beszéljük meg Hierholzer 1873-as dolgozatának algoritmusát , amely a bizonyításának gondolatát követi (lásd fentebb a közvetett jelentést). Megismétli az áramkörök kinyerését, amelyeket ragasztunk egy euleri áramkör felépítéséhez. Ez az algoritmus megvalósítható annak érdekében, hogy egy algoritmus lineáris időben legyen az élek számában (lásd: 2.5.2. Példa és 2.3.1. Algoritmus). Ehhez a következő műveleteket csak állandó időben kell végrehajtani:

1. nem kölcsönzött élt találni
2. keressen egy új csúcsot, amely még mindig beengedi a véletlenszerű éleket
3. illessze be az áramkört az épülő pályára

Ehhez elegendő hatékonyan fenntartani a kétszeresen összekapcsolt listákat  :

1. az épülő pálya azon csúcsainak felsorolása, amelyeknek még nincsenek élei
2. minden csúcsnál a még nem használt élek listája
3. az épülő út széleinek listája

Fleury algoritmusa

Pierre-Henry Fleury 1883-ban adott egy másik algoritmust, de a számítógépen történő megvalósítás kevésbé lenne hatékony, mint Hierholzer algoritmusa. Ötlete az, hogy kiépítse az áramkört úgy, hogy minden alkalommal elsőbbségként kölcsönad egy olyan élt, amelynek törlése nem szakítja meg a gráfot.

Irányított gráf esete

A fenti eredményeket irányított grafikonokba exportáljuk. Egy ilyen gráfról azt mondják, hogy Eulerian, ha a következő tulajdonsággal rendelkezik:

A gráf íveit úgy tudjuk elrendezni, hogy a sorrendhez képest két egymást követő él - ahol a sorrend utolsó és első éle egymást követőnek tekinthető - egymás után következzenek a gráfban.

Itt is ez a tulajdonság azt jelenti, hogy „áthaladhatunk” a grafikonon, ha követjük az íveket a kezdeti végüktől a terminál végéig, és természetesen minden ívet pontosan egyszer használunk, és visszatérünk a kiindulási ponthoz. Ami a nem orientált verziót illeti, a következő tételt mutatjuk be:

Euler tétele (orientált változat)  -  Legyen G orientált gráf. A következő három tétel egyenértékű:

• G jelentése euleriánus;
• G szorosan kapcsolódik, és minden csúcsa azonos számú él kezdő és végső vége;
• G összekapcsolt állapotban van, és minden csúcsa azonos számú él kezdő és végső vége.

A kapcsolhatóság elegendő ahhoz, hogy a nem irányított eset kiterjedjen az irányított esetre, és egy euleri gráf szükségszerűen szorosan kapcsolódik egymáshoz.

Algoritmikus összetettség

Egyes algoritmikus könyvekben (de a Diestel-féle gráfelméleti könyvben is, lásd 10. fejezet, 213. o.) A bonyolultságelmélet keretein belül az EULERIAN problémát, hogy egy gráf Eulerian-e, gyakran összehasonlítják a HAMILTONIAN problémával, egy hamiltoni pálya , vagyis minden csúcs mellett pontosan egyszer haladó pálya. Annak megállapítása, hogy egy gráf elfogadja-e az euleri kört, polinomiális időben történik (elegendő a grafikon csúcsainak paritását ellenőrizni). Így az Euler-probléma, hogy egy gráf Eulerian-e, a P osztályba tartozik . A HAMILTONIAN problémát eleve bonyolultabban lehet algoritmikusan megoldani: NP-teljes probléma , fontos alkalmazásokkal.

Hivatkozások

1. (a) Patrick Bosc , Marc Guyomard és Laurent Miclet , algoritmusok tervezési elvek és 150 korrigálatlan gyakorlatok ,2016( online olvasás )
2. (la) Leonhard Euler, "  " Solutio problematis ad geometriam situs relevantis "  " , Megjegyzés. Academiae Sci. I. Petropolitanae 8 ,1736, P.  128–140 ( online olvasás )
3. algoritmikus ,2021. február 28( online olvasás )
4. "EULERIAN WAY - Unicursal figurák": "A HÍRES KERET és változatok" , SZÁMOKON - Érdekességek, elmélet és felhasználások .
5. „  Königsbergi hidak és az euleri ciklus  ” , a www.bibmath.net webhelyen (elérhető : 2021. február 26. )
6. (de) Carl Hierholzer és Chr Wiener , "  Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren  " , Mathematische Annalen , vol.  6, n o  1,1 st március 1873, P.  30–32 ( ISSN  1432-1807 , DOI  10.1007 / BF01442866 , online olvasás , hozzáférés : 2021. február 26. )
7. (hu-HU) Reinhard Diestel , "  Grafikonelmélet  " , matematikai diplomaszövegek ,2017( ISSN  0072-5285 és 2197-5612 , DOI  10.1007 / 978-3-662-53622-3 , online olvasás , hozzáférés 2021. március 2. )
8. Fleischner, Herbert (1991), "X.1 algoritmusok az euleri ösvényekhez", euleri grafikonok és kapcsolódó témák: 1. rész, 2. kötet, Annals of Discrete Mathematics, 50, Elsevier, pp. X.1–13. ( ISBN  978-0-444-89110-5 ) .
9. (a) Dieter Jungnickel , grafikonok, Networks és algoritmusok , Springer-Verlag, al.  "Algoritmusok és számítás a matematikában",2008( ISBN  978-3-642-09186-5 , online olvasás )
10. Fleury, Pierre-Henry (1883), "A helyzetgeometria két problémája", Journal of Elementary Mathematics, 2. szer. (franciául), 2: 257–261.
11. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest és Clifford Stein, Bevezetés az algoritmikába , Dunod,2004, 2 nd  ed. , 1176  p. ( ISBN  2 10 003922 9 )
12. (a) Sanjoy Dasgupta, Christos Papadimitriou és Umesh Vazirani, Algoritmusok , McGraw-Hill,2008

Lásd is

Kapcsolódó cikkek

• Kínai postás probléma (amely abból áll, hogy keressen egy utat, amely legalább egyszer elhalad minden él mellett)

• A BEST tétel , amely képletet ad egy gráf Euler-áramköreinek számához
• Az Euler nevét viselő alanyok listája

Bibliográfia

• (en) Reinhard Diestel , Grafikonelmélet [ a kiadások részlete ]
• Édouard Lucas , Matematikai kikapcsolódás, 9 rue de Médicis, Párizs, Albert Banchard könyvesbolt,1892( online olvasás )olvassa online a Gallica-n , lásd: p. "  33. oldal  ", ahol a problémát Párizs hídjai címmel írják le 1880-ban .