V prvej lekcii, pri predstavovaní pojmu graf, sme ako príklad považovali súťaž športových tímov. my. spojil dva tímy, povedzme A a C, s okrajom AC v prípade, že tieto tímy už hrali medzi sebou. Takýto graf však neodpovedá na jednu veľmi dôležitú otázku: kto presne vyhral hru?
Tento nedostatok sa dá ľahko odstrániť. Ak tím A vyhral nad C, dohodneme sa, že umiestnime šípku na hranu AC smerujúcu z A do C. Predpokladajme, že poznáme výsledky všetkých už odohratých hier a do grafu pridáme obr. 1 zodpovedajúce šípky; Nech je výsledkom graf znázornený na obr. 58.

Obrázok 58.

Tento graf ukazuje, že tím A porazil C, tím F prehral s A a tím B vyhral všetky zápasy proti C, E, F atď.

Hrana sa volá graf orientovaný, ak sa berie do úvahy jeden vrchol začiatok rebra a druhý - koniec.
Nazýva sa graf, ktorého všetky hrany sú orientované orientáciapočítať.
Ten istý vrchol orientovaného grafu môže slúžiť ako začiatok pre niektoré hrany a koniec pre iné. Podľa toho sa rozlišujú dva stupne vrcholu: výstupný stupeň a vstupný stupeň.
Výstupný stupeň vrchol A orientovaného grafu je počet hrán opúšťajúcich A (zápis: d+(A)).
Stupeň vstupu vrcholu A orientovaného grafu je počet záznamov v ALE hrany (symbol: d-(A)).
Čo ak sa zápas skončí remízou? Výsledky nerozhodného výsledku môžeme premietnuť do grafu tak, že príslušné hrany ponecháme bez orientácie. Pri tom získame tzv smshanny gróf, ktorý má smerované aj neusmernené okraje.
Cesta v orientovanom grafe G od A1 do An je postupnosť orientovaných hrán<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>tak, že koniec každej predchádzajúcej hrany sa zhoduje so začiatkom ďalšej a žiadna hrana sa nevyskytuje viackrát.

Ryža. 59
Ak v orientovanom grafe G existuje cesta z ALE do B, potom späť z AT do ALE nemusí byť (obr. 59).
Ak existuje smerovaná cesta z A do B, potom sa hovorí, že B je dosahma od A
V stĺpci G na obrázku 38 je možné dosiahnuť B
z A, A nie je dosiahnuteľné z B.
jednoduchý spôsob Orientovaný graf je cesta, v ktorej nie je žiadny vrchol obsiahnutý viac ako raz. uzavretá cesta v orientovanom grafe sa nazýva riadený cyklus.
dlhá cesta je počet hrán v tejto ceste.
Vzdialenosť z A do B v orientovanom grafe je dĺžka najkratšej cesty z A do B. Ak cesta z A do B neexistuje, potom sa vzdialenosť z A do B nazýva nekonečná a označuje sa?. Vzdialenosť z A do B bude označená S (AB). Pre graf na obrázku 38
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d ?.
Problém 9.1.
V prímorskom letovisku sa po zriadení jednosmernej premávky ukázalo, že počet ulíc, ktorými môžete vstúpiť do každej križovatky, sa rovná počtu ulíc, ktorými ju môžete opustiť. Dokážte, že je možné navrhnúť obchádzkovú trasu, ktorá začína a končí na rovnakom mieste a prechádza každým úsekom ulice práve raz.
rozhodnutie.
Zostrojme digraf G, ktorý definuje pohyb v meste.
Digraf sa nazýva pripojený, ak je možné prejsť z ktoréhokoľvek z jeho vrcholov do akéhokoľvek iného pozdĺž oblúkov bez toho, aby sa brala do úvahy ich orientácia. Súvislý digraf sa nazýva Euler, ak má Eulerov cyklus.
Veta 12. Súvislý digraf je Euler práve vtedy a len vtedy, ak pre každý z jeho vrcholovvrovnosťd- (v) = d+ (v) .
Veta je dokázaná presne rovnakým spôsobom ako veta v úlohe 4.2.
Z podmienok úlohy vyplýva, že pre vrcholy zostrojeného grafu G je splnená rovnosť d-(v) = d+(v). Preto Eulerov graf G a Eulerov cyklus určia požadovanú trasu hliadky.
Problém 9.2.
Na rovine je vyznačený konečný počet bodov. Niektoré dvojice bodov sú začiatky a konce vektorov a počet vektorov vstupujúcich do akéhokoľvek bodu sa rovná počtu vektorov, ktoré ho opúšťajú. Nájdite súčet vektorov.
rozhodnutie.
Body roviny spolu s vektormi tvoria digraf G. Cyklus digrafu, ktorého všetky vrcholy sú rôzne, je tzv. obrys.
Veta 13. Súvislý digrafGEuler vtedy a len vtedyGje spojenie obrysov, ktoré po pároch nemajú spoločné hrany.
Dôkaz. Nevyhnutnosť. Nech G je Eulerov digraf. Zvážte jeho ľubovoľný vrchol u1. Nechajme vrchol u1 pozdĺž nejakého oblúka (u1, u2), čo sa dá urobiť, keďže digraf G je súvislý. Keďže d-(u2) = d+(u2), je možné ponechať vrchol u2 pozdĺž oblúka (u2, u3) . Digraf G má konečný počet vrcholov, takže skončíme na nejakom vrchole w, kde sme boli predtým. Časť reťazca, ktorá začína a končí na w, je cesta C1. Odstráňte oblúky obrysu C1 z digrafu G . Vo výslednom digrafe G1 (pravdepodobne rozpojenom) sa vstupné a výstupné stupne vrcholov patriacich do C znížili o jednu, vstupné a výstupné stupne zostávajúcich vrcholov sa nezmenili. Preto pre ľubovoľný vrchol v digrafu C1 bude platiť rovnosť d-(v) = d+(v). Preto v digrafe G1 môžeme vyčleniť obrys C 2 atď.
Dostatočnosť sa dokazuje spojením kontúr do Eulerovho cyklu (pozri dôkaz vety v úlohe 4.2).
Veta bola dokázaná. Možno digraf G definujúci vektory v našom probléme nesúvisí. Aplikovaním dokázanej vety na každú spojenú časť digrafu získame rozdelenie vektorov do vrstevníc. Súčet vektorov prislúchajúcich jednému obrysu sa rovná nule. Preto sa súčet všetkých vektorov rovná nule.

Predtým, ako začnete priamo študovať algoritmy, musíte mať základné znalosti o samotných grafoch, aby ste pochopili, ako sú reprezentované v počítači. Tu nebudú podrobne popísané všetky aspekty teórie grafov (nie je to potrebné), ale iba tie, ktorých neznalosť výrazne skomplikuje asimiláciu tejto oblasti programovania.

Niekoľko príkladov poskytne trochu povrchnú predstavu o grafe. Typickým grafom je teda mapa metra alebo nejaká iná trasa. Programátor pozná najmä počítačovú sieť, ktorá je tiež grafom. Spoločná vec je tu prítomnosť bodiek spojených čiarami. Takže v počítačovej sieti sú body samostatné servery a linky sú rôzne typy elektrických signálov. V metre sú prvé stanice, druhým sú tunely položené medzi nimi. V teórii grafov sa body nazývajú vrcholy (uzly) a čiary rebrá (oblúky). teda graf je súbor vrcholov spojených hranami.

Matematika nepracuje s obsahom vecí, ale s ich štruktúrou, abstrahuje ju od všetkého, čo je dané ako celok. Pomocou tejto techniky môžeme o niektorých objektoch usudzovať ako o grafoch. A keďže teória grafov je súčasťou matematiky, potom pre ňu vôbec nezáleží na tom, čo je v princípe objekt; dôležité je len to, či ide o graf, teda či má vlastnosti požadované pre grafy. Preto pred uvedením príkladov v posudzovanom objekte vyčleňujeme len to, čo nám podľa nášho názoru umožní ukázať analógiu, hľadáme niečo spoločné.

Vráťme sa k počítačovej sieti. Má určitú topológiu a môže byť podmienene znázornený ako množstvo počítačov a ciest, ktoré ich spájajú. Obrázok nižšie ukazuje ako príklad plne prepojenú topológiu.

Je to v podstate graf. Päť počítačov sú vrcholy a spojenia (signálne cesty) medzi nimi sú hrany. Nahradením počítačov vrcholmi dostaneme matematický objekt - graf, ktorý má 10 hrán a 5 vrcholov. Vrcholy môžete očíslovať ľubovoľne a nie nevyhnutne tak, ako sa to robí na obrázku. Stojí za zmienku, že v tomto príklade nie sú použité žiadne slučky, teda taká hrana, ktorá opúšťa vrchol a okamžite do neho vstupuje, ale v problémoch sa môžu vyskytnúť slučky.

Tu je niekoľko dôležitých označení používaných v teórii grafov:

• G=(V, E), tu G je graf, V sú jeho vrcholy a E sú hrany;
• |V| – poradie (počet vrcholov);
• |E| – veľkosť grafu (počet hrán).

V našom prípade (obr. 1) |V|=5, |E|=10;

Keď je akýkoľvek iný vrchol dostupný z akéhokoľvek vrcholu, potom sa takýto graf volá neorientovaný spojený graf (obr. 1). Ak je graf spojený, ale táto podmienka nie je splnená, potom sa takýto graf volá orientovaný alebo digraf (obr. 2).

Orientované a neorientované grafy majú pojem stupňa vrcholu. Stupeň vertexu je počet hrán, ktoré ho spájajú s inými vrcholmi. Súčet všetkých stupňov grafu sa rovná dvojnásobku počtu všetkých jeho hrán. Na obrázku 2 je súčet všetkých mocnín 20.

V digrafe, na rozdiel od neorientovaného grafu, je možné prejsť z vrcholu h do vrcholu s bez medziľahlých vrcholov, iba ak hrana opustí h a vstúpi do s, ale nie naopak.

Orientované grafy majú nasledujúci zápis:

G=(V, A), kde V sú vrcholy, A sú orientované hrany.

Tretí typ grafov - zmiešané grafy (obr. 3). Majú orientované aj nesmerové hrany. Formálne je zmiešaný graf napísaný takto: G=(V, E, A), kde každé z písmen v zátvorke označuje aj to, čo sa mu predtým pripisovalo.

V grafe na obrázku 3 sú niektoré oblúky smerované [(e, a), (e, c), (a, b), (c, a), (d, b)], iné nie sú smerované [( e, d), (e, b), (d, c)…].

Dva a viac grafov sa na prvý pohľad môže zdať rozdielne svojou štruktúrou, ktorá vzniká ich rozdielnym znázornením. Ale nie vždy to tak je. Zoberme si dva grafy (obr. 4).

Sú si navzájom ekvivalentné, pretože bez zmeny štruktúry jedného grafu môžete zostaviť ďalší. Takéto grafy sa nazývajú izomorfný, teda majúci tú vlastnosť, že každý vrchol s určitým počtom hrán v jednom grafe má rovnaký vrchol v inom. Obrázok 4 ukazuje dva izomorfné grafy.

Keď je každej hrane grafu priradená nejaká hodnota, ktorá sa nazýva váha hrany, potom takýto graf pozastavená. V rôznych úlohách môžu rôzne typy meraní pôsobiť ako váhy, napríklad dĺžky, ceny trás atď. V grafickom znázornení grafu sú hodnoty hmotnosti zvyčajne uvedené vedľa okrajov.

V ktoromkoľvek z grafov, ktoré sme zvážili, je možné vybrať cestu a navyše viac ako jednu. spôsob je postupnosť vrcholov, z ktorých každý je spojený s nasledujúcim pomocou hrany. Ak sa prvý a posledný vrchol zhodujú, potom sa takáto cesta nazýva cyklus. Dĺžka cesty je určená počtom hrán, ktoré ju tvoria. Napríklad na obrázku 4.a je cesta sekvenciou [(e), (a), (b), (c)]. Táto cesta je podgrafom, pretože sa na ňu vzťahuje definícia toho druhého, a to: graf G'=(V', E') je podgrafom grafu G=(V, E) iba ak V' a E' patria V, E .

Typy grafov môžu byť určené všeobecnými princípmi ich konštrukcie (napríklad bipartitný graf a Eulerov graf), alebo môžu závisieť od určitých vlastností vrcholov alebo hrán (napríklad orientovaný a neorientovaný graf, obyčajný graf). ).

Riadené a neorientované grafy

odkazy(poradie dvoch koncov okraja grafu nie je podstatné). neorientovaný .

Grafy, v ktorých sú všetky hrany oblúky(poradie dvoch koncov hrany grafu je významné). orientované grafy alebo digrafy .

Neorientovaný graf môžu byť prezentované vo forme orientovaný graf , ak je každý z jeho článkov nahradený dvoma oblúkmi s opačnými smermi.

Slučkové grafy, zmiešané grafy, prázdne grafy, multigrafy, bežné grafy, kompletné grafy

Ak graf obsahuje slučky, potom je táto okolnosť špecificky stanovená pridaním slov "so slučkami" k hlavnej charakteristike grafu, napríklad "digraf so slučkami". Ak graf neobsahuje slučky, pridajú sa slová „bez slučiek“.

zmiešané sa nazýva graf, v ktorom sú hrany aspoň dvoch z troch spomínaných variet (linky, oblúky, slučky).

Graf pozostávajúci iba z holé vrcholy, sa volá prázdny .

Multigraf sa nazýva graf, v ktorom môžu byť dvojice vrcholov spojené viacerými hranami, teda obsahujúcimi viaceré hrany, ale bez slučiek.

Volá sa graf bez oblúkov (teda neorientovaný), bez slučiek a viacerých hrán obyčajný . Bežný graf je znázornený na obrázku nižšie.

Graf daného typu sa nazýva kompletný , ak obsahuje všetky hrany možné pre tento typ (s rovnakou množinou vrcholov). Takže v úplnom obyčajnom grafe je každá dvojica rôznych vrcholov spojená práve jedným prepojením (obrázok nižšie).

bipartitný graf

Graf sa nazýva bipartitný , ak množinu jej vrcholov možno rozdeliť na dve podmnožiny tak, že žiadna hrana nespája vrcholy tej istej podmnožiny.

Príklad 1 Stavať plný bipartitný graf.

Kompletný bipartitný graf pozostáva z dvoch množín vrcholov a všetkých možných väzieb spájajúcich vrcholy jednej množiny s vrcholmi inej množiny (obrázok nižšie).

eulerov graf

Už sme sa dotkli problémy týkajúce sa Königsbergských mostov. Eulerovo negatívne riešenie tohto problému viedlo k prvej publikovanej práci o teórii grafov. Problém prechodu mosta možno zovšeobecniť a získať nasledujúci problém teórie grafov: je možné v danom grafe nájsť cyklus, ktorý obsahuje všetky vrcholy a všetky hrany? Graf, v ktorom je to možné, sa nazýva Eulerov graf.

takze Eulerov graf sa nazýva graf, v ktorom je možné obehnúť všetky vrcholy a zároveň prejsť jednou hranou iba raz. V ňom musí mať každý vrchol len párny počet hrán.

Príklad 2 Je úplný graf s rovnakým číslom n hrany, ku ktorým je každý vrchol incidentný, Eulerov graf? Vysvetlite odpoveď. Uveďte príklady.

Odpoveď. Ak n je nepárne číslo, potom je každý vrchol incidentný n- 1 rebrá. V tomto prípade je daný graf Eulerovým grafom. Príklady takýchto grafov sú uvedené nižšie.

Pravidelný graf

pravidelný graf je súvislý graf, ktorého všetky vrcholy majú rovnaký stupeň k. Na obrázku napríklad 2 sú teda znázornené príklady pravidelných grafov, ktoré sa podľa stupňa vrcholov nazývajú 4-pravidelné a 2-regulárne grafy alebo pravidelné grafy 4. stupňa a 2. stupňa.

Počet vrcholov v bežnom grafe k-tý stupeň nemôže byť nižší k+1. Pravidelný graf nepárneho stupňa môže mať len párny počet vrcholov.

Príklad 3 Zostrojte pravidelný graf, v ktorom má najkratší cyklus dĺžku 4.

rozhodnutie. Argumentujeme nasledovne: na to, aby dĺžka cyklu splnila danú podmienku, je potrebné, aby počet vrcholov grafu bol násobkom štyroch. Ak je počet vrcholov štyri, potom sa získa graf znázornený na obrázku nižšie. Je pravidelný, ale jeho najkratší cyklus má dĺžku 3.

Zvýšte počet vrcholov na osem (ďalšie číslo je násobkom štyroch). Vrcholy spojíme hranami tak, aby sa stupne vrcholov rovnali trom. Získame nasledujúci graf, ktorý vyhovuje podmienkam úlohy.

hamiltonovský graf

Hamiltonov graf sa nazýva graf obsahujúci hamiltonovský cyklus. Hamiltonov cyklus sa nazýva jednoduchý cyklus prechádzajúci všetkými vrcholmi uvažovaného grafu. Zjednodušene povedané, hamiltonovský graf je graf, v ktorom je možné prejsť všetkými vrcholmi a každý vrchol sa počas prechodu opakuje iba raz. Príklad hamiltonovského grafu je na obrázku nižšie.

Príklad 4 Vzhľadom na bipartitný graf, v ktorom n- počet vrcholov z množiny A, a m- počet vrcholov z množiny B. V ktorom prípade ide o eulerovský graf a v ktorom o hamiltonovský graf?

V predchádzajúcich kapitolách sme predstavili niektoré z hlavných výsledkov teórie neorientovaných grafov. Neorientované grafy však na popis niektorých situácií nestačia. Napríklad pri znázornení dopravnej mapy pomocou grafu, ktorého okraje zodpovedajú uliciam, treba okrajom priradiť orientáciu, ktorá označuje prípustný smer pohybu. Ďalším príkladom je počítačový program modelovaný grafom, ktorého hrany predstavujú tok riadenia z jednej sady inštrukcií do druhej. V tejto reprezentácii programu musia byť hrany tiež orientované tak, aby indikovali smer riadiaceho toku. Ďalším príkladom fyzického systému, ktorý vyžaduje na zobrazenie orientovaný graf, je elektrický obvod. Aplikácie orientovaných grafov a súvisiacich algoritmov sú diskutované v kap. 11-15.

Táto kapitola predstavuje hlavné výsledky teórie orientovaných grafov. Diskutované sú otázky súvisiace s existenciou orientovaných Eulerových reťazcov a hamiltonovských cyklov. Uvažuje sa aj o orientovaných stromoch a ich spojení s orientovanými Eulerovými reťazami.

5.1. Základné definície a pojmy

Začnime predstavením niekoľkých základných definícií a pojmov súvisiacich s orientovanými grafmi.

Orientovaný graf pozostáva z dvoch množín: z konečnej množiny V, ktorej prvky sa nazývajú vrcholy, a z konečnej množiny E, ktorej prvky sa nazývajú hrany alebo oblúky. Každý oblúk je spojený s usporiadaným párom vrcholov.

Symboly sa používajú na označenie vrcholov a symboly sa používajú na označenie oblúkov. Ak , potom sa nazývajú koncové vrcholy a - počiatočný vrchol, - koncový vrchol . Všetky oblúky, ktoré majú rovnaký pár začiatočných a koncových vrcholov, sa nazývajú rovnobežné. Oblúk sa nazýva slučka, ak vrchol incidentu je jeho počiatočným aj koncovým vrcholom.

V grafickom znázornení orientovaného grafu sú vrcholy znázornené bodkami alebo kruhmi a hrany (oblúky) sú znázornené segmentmi.

čiary spájajúce bodky alebo kruhy predstavujúce ich koncové body. Okrem toho majú oblúky priradenú orientáciu, ktorá je označená šípkou smerujúcou z počiatočného vrcholu do koncového vrcholu.

Napríklad, ak je to Ich), môže byť orientovaný graf znázornený na obr. 5.1. V tomto grafe - rovnobežné oblúky a - slučka.

Ryža. 5.1. Orientovaný graf.

Hovorí sa, že oblúk prechádza do jeho koncových vrcholov. Vrcholy sa nazývajú susedné, ak sú koncové pre jeden oblúk. Ak majú oblúky spoločný koncový vrchol, potom sa nazývajú susedné.

Oblúk sa nazýva vychádzajúci zo svojho počiatočného vrcholu a vstupujúci do jeho konečného vrcholu. O vrchole sa hovorí, že je izolovaný, ak nemá žiadne dopadajúce oblúky.

Stupeň vrcholu je počet oblúkov, ktoré k nemu dopadajú. In-stupeň vrcholu je počet oblúkov vstupujúcich do V] a vonkajší stupeň je počet odchádzajúcich oblúkov. Symboly a b" označujú minimálny vonkajší stupeň a mierny stupeň orientovaného grafu. Podobne symboly označujú maximálny vonkajší stupeň a najvyšší stupeň.

Množiny ľubovoľného vrcholu sú definované takto: . Napríklad v grafe na obr. 5.1.

Všimnite si, že slučka zväčšuje polstupne vstupu aj výstupu z tohto vrcholu. Nasledujúce tvrdenie je dôsledkom skutočnosti, že každý oblúk sa zväčší o 1 súčet polstupňov vstupu aj výstupu orientovaného grafu.

Veta 5.1. V orientovanom grafe s oblúkmi

Súčet stupňov = Súčet stupňov = m.

Podgrafy a vygenerované podgrafy orientovaného grafu sú definované rovnakým spôsobom ako v prípade neorientovaných grafov (kapitola 1.2).

Neorientovaný graf, ktorý je výsledkom odstránenia orientácie z oblúkov orientovaného grafu G, sa nazýva podkladový neorientovaný graf G a označuje sa .

Smerovaná cesta orientovaného grafu je konečná postupnosť vrcholov

Čo je oblúk grafu G. Takáto trasa sa zvyčajne nazýva riadená -trasa a počiatočný vrchol je konečným vrcholom trasy a všetky ostatné vrcholy sú vnútorné. Začiatočné a koncové vrcholy nasmerovanej cesty sa nazývajú jej koncové vrcholy. Všimnite si, že oblúky, a teda aj vrcholy, sa môžu v nasmerovanej ceste objaviť viackrát.

O orientovanej trase sa hovorí, že je otvorená, ak sú jej koncové vrcholy odlišné, inak sa nazýva uzavretá.

Orientovaná cesta sa nazýva orientovaná cesta, ak sú všetky jej oblúky zreteľné. Orientovaná cesta je otvorená, ak sú jej koncové body odlišné, inak je uzavretá.

Otvorená orientovaná cesta sa nazýva orientovaná cesta, ak sú všetky jej vrcholy odlišné.

Uzavretý orientovaný reťazec sa nazýva orientovaný cyklus alebo obrys, ak sú jeho vrcholy, s výnimkou koncových, odlišné.

O orientovanom grafe sa hovorí, že je acyklický alebo bez obrysov, ak nemá žiadne obrysy. Napríklad orientovaný graf na obr. 1 je acyklický. 5.2.

Ryža. 5.2. Acyklický orientovaný graf.

Ryža. 5.3. Silne prepojený orientovaný graf.

Postupnosť vrcholov v orientovanom grafe G sa nazýva cesta v G, ak ide o cestu v podkladovom neorientovanom grafe. Napríklad postupnosť v grafe na obr. 5.2 je trasa, ale nie je orientovaná.

Reťazec, dráha a cyklus orientovaného grafu sú definované podobne.

O orientovanom grafe sa hovorí, že je spojený, ak je pripojený podkladový neorientovaný graf.

Podgraf orientovaného grafu G sa nazýva komponent grafu G, ak je komponentom grafu

O vrcholoch orientovaného grafu G sa hovorí, že sú silne spojené, ak existujú smerované cesty z a späť do G. Ak je silne spojené s potom, je zrejmé, že je silne spojené s . Každý vrchol je pevne spojený sám so sebou.

Ak je vrchol pevne spojený s vrcholom, potom, ako je ľahké vidieť, vrchol je pevne spojený s vrcholom. Preto v tomto prípade jednoducho povieme, že vrcholy sú pevne spojené.

O orientovanom grafe sa hovorí, že je silne spojený, ak sú všetky jeho vrcholy silne spojené. Napríklad graf na obr. 5.3.

Maximálny silne spojený podgraf orientovaného grafu G sa nazýva silne spojený komponent G. Ak je smerovaný graf silne spojený, potom má jeden silne spojený komponent, a to sám seba.

Zvážte orientovaný graf. Je ľahké vidieť, že každý jeho vrchol patrí práve jednému silne prepojenému komponentu grafu G. Preto množiny vrcholov silne spojených komponentov tvoria oddiel množiny vrcholov Y grafu.

Ryža. 5.4. Graf a jeho kondenzácia.

Napríklad orientovaný graf na obr. 5.4, ​​​​a má tri silne spojené komponenty s množinami vrcholov a tvoriace oddiel množiny vrcholov orientovaného grafu.

Je zaujímavé, že orientovaný graf môže obsahovať oblúky, ktoré nie sú zahrnuté v žiadnych silne prepojených komponentoch grafu. Napríklad žiadne silne spojené komponenty neobsahujú oblúky v grafe na obr. 5.4, ​​a.

Aj keď vlastnosť „silne prepojená“ znamená rozdelenie množiny vrcholov grafu, nemusí generovať rozdelenie množiny oblúkov.

Zjednotenie, prienik, súčet mod 2 a ďalšie operácie s orientovanými grafmi sú definované presne rovnakým spôsobom ako v prípade neorientovaných grafov (kapitola 1.5).

Graf, ktorý vznikne kontrakciou všetkých oblúkov silne spojených komponentov orientovaného grafu G, sa nazýva kondenzovaný graf grafu G. Kondenzácia grafu znázorneného na obr. 5.4, ​​​​a, je znázornený na obr. 5.4b.

Vrcholy grafu zodpovedajú silne prepojeným komponentom grafu G a nazývame ich kondenzované obrazy komponentov.

Poradie a cyklomatické číslo orientovaného grafu sú rovnaké ako hodnoty zodpovedajúceho neorientovaného grafu. To znamená, že ak má orientovaný graf G oblúky, vrcholy a komponenty, potom poradie a cyklomatické číslo grafu G sú dané vzťahom

Teraz definujeme minimálne spojené orientované grafy a študujeme niektoré z ich vlastností.

O orientovanom grafe G sa hovorí, že je minimálne spojený, ak je silne spojený, a odstránením akéhokoľvek oblúka sa zbavuje jeho silne prepojenej vlastnosti.

Ryža. 5.5. Minimálne pripojený orientovaný graf.

Minimálne pripojený je napríklad graf na obr. 5.5.

Je zrejmé, že minimálne spojené grafy nemôžu mať paralelné oblúky a slučky.

Vieme, že neorientovaný graf je minimálne spojený práve vtedy, ak ide o strom (Pr. 2.13). Podľa vety 2.5 má strom aspoň dva vrcholy stupňa 1. Preto minimálne spojené neorientované grafy majú aspoň dva vrcholy stupňa 1.

Urobme podobný výsledok pre orientované grafy. Stupeň ktoréhokoľvek vrcholu silne prepojeného orientovaného grafu musí byť aspoň 2, pretože každý vrchol musí mať odchádzajúce a prichádzajúce oblúky. V nasledujúcej vete dokážeme, že minimálne súvislý orientovaný graf má aspoň dva vrcholy stupňa 2.

Hrana je usporiadaná dvojica vrcholov. Nazýva sa graf, pre ktorý je naznačený smer každej z jeho hrán orientovaný.

Jednoznačne aplikácia na turnaje. Napríklad šípka prechádza od porazeného tímu k víťaznému, takže orientovaný graf ukazuje nielen to, kto s kým hral, ​​ale aj kto vyhral.

Je tiež možné definovať postupnosť alebo preferenčný vzťah pomocou orientovaných grafov.

Napríklad, v grafoch algoritmov vrcholy grafu zodpovedajú vykonávaná operácia, a oblúky (orientované hrany) zodpovedajú dátové závislosti(t.j. aké vstupy sú potrebné na vykonanie operácie).

Napríklad pri komplexnom vyhodnocovaní vzoriek (napríklad v geológii) naznačuje smer hrany preferenciu. Normálny preferenčný systém by nemal mať cykly.

Tanya Natasha

aby ste si vždy mohli vybrať, inak musíte prehodnotiť systém preferencií.

Jednosmerka.

Cestná mapa so smerom jazdy poskytuje špeciálne príklady orientovaných grafov. Aby sme sa vysporiadali s obojsmernými cestami, namiesto jednej cesty (alebo namiesto jednej neorientovanej hrany) zavedieme dve smerované hrany spájajúce rovnaké vrcholy a majúce opačné smery.

Otázkou je, za akých podmienok môžu byť ulice mesta orientované tak, aby sa dalo jazdiť z akéhokoľvek bodu na akékoľvek iné bez toho, aby sa porušovali pravidlá premávky po uliciach.

V jazyku teórie grafov je to formulované takto: za akej podmienky môžu byť hrany grafu G orientované tak, aby pre ktorúkoľvek dvojicu jeho vrcholov existovala orientovaná cesta, ktorá ich spája?

Je jasné, že každý takýto graf musí byť prepojený, ale to nestačí.

Zavolá sa hrana E = (A, B). spojovacia hrana, alebo isthmus ak je to jediná cesta z A do B (alebo naopak).

Spojovacia hrana rozdeľuje všetky vrcholy grafu na dve množiny: tie, ktoré sú dosiahnuteľné z A bez prechodu pozdĺž hrany E a tie, ktoré je možné dosiahnuť z B bez prechodu pozdĺž E. Graf sa v tomto prípade skladá z dvoch častí G 1 a G 2 spojené iba hranou E (obr. a a a+1).

Na mape mesta je spojovacie rebro jedinou diaľnicou spájajúcou samostatné časti mesta. Je jasné, že ak sa na takejto diaľnici zriadi jednosmerná premávka, potom by nebol prechod z jednej mestskej časti do druhej.

Ak hrana E i = (A i, B i) nespája, potom existuje ďalšia cesta, ktorá spája A i a B i a neprechádza cez E i. Preto sa takáto hrana bude nazývať cyklická hrana.

obr.2 Pripojenie obr. 2+1 Záver (spájanie) Obr. 2+2 Cykl

rebro rebro

Veta 1 Ak G- súvislého grafu, potom je vždy možné orientovať cyklické hrany z G , pričom spojovacie hrany ponecháme bez smeru, takže ľubovoľná dvojica vrcholov v tomto grafe môže byť spojená usmernenou cestou.

Pre územný plán mesta možno toto tvrdenie formulovať takto: ak je obojsmerná premávka ponechaná len na mostoch (za predpokladu, že tento most je jediným mostom cez rieku) a na slepých uličkách, potom na všetkých ostatných uliciach je jednosmerná premávka možno zriadiť tak, aby doprava zabezpečovala komunikáciu všetkých častí mesta.

Túto vetu môžeme dokázať tým, že ukážeme spôsob, ako správne orientovať graf. Vyberme si G ľubovoľná hrana E \u003d (A, B) . Ak E - spojovacia hrana, zostane obojstranná a potom bude možné z nej prejsť ALE do AT a späť (obr. 2+3).

obr.2+3 obr. 2+4

Ak E je cyklická hrana, potom je zaradená do nejakého cyklu S, na ktorom môžete nastaviť cyklickú orientáciu (obr.2+4).

Predpokladajme, že sme už nejakú časť zorientovali H počítať G, tak, že z ľubovoľného vrcholu grafu H môžete prejsť na ktorýkoľvek iný jeho vrchol pri dodržaní pravidiel jednosmernej premávky. Od grafu G je pripojený, potom buď H zodpovedá celému grafu g, alebo je tam hrana E \u003d (A, B), čo nepatrí H , ale jeden z jeho vrcholov, povedzme ALE , patrí H .

Ak E - spojovacie rebro AB , potom zostane obojstranný. Potom pre ľubovoľný vrchol X počítať H možno nájsť orientovaný reťazec R pripojenie X s A , čo znamená (cez okraj E ) a s AT . Späť zhora AT za hranicou E môžete ísť do ALE a potom - pozdĺž orientačného reťazca Z - od ALE do X (Obrázok a+5). Prikladanie E do H , dostaneme väčšinu grafu G s požadovanými vlastnosťami. Ak okraj E \u003d (A, B) je cyklický, patrí do nejakého cyklu S . Udávame smer pre S od ALE predtým AT a ďalej S k prvému vrcholu D od S vo vlastníctve H (Obr. a+6).

ryža. a+5 obr. a+6

Pridajme všetky tieto okraje k H . Nechať byť X - ľubovoľný vrchol z H , a o - ľubovoľný vrchol S ; možno nájsť orientovaný reťazec R , vo vlastníctve H a pripojenie X s ALE a potom spolu S ísť na vrchol o od S . Späť z o môžete ísť spolu S navrchol D , a z toho - spolupatričnosť H orientovaný reťazec Z - od D do X . Preto orientovaný graf získaný pridaním do H špecifikované hrany cyklu S , tiež spĺňa požadované podmienky. Pokračujúc v tomto procese nakoniec pôvodný graf orientujeme požadovaným spôsobom G .

Vertexové stupne.

Pre orientované grafy máme v každom vrchole počet p(A) odchádzajúcich a počet p*(A) prichádzajúcich hrán. Celkový počet hrán je:

N \u003d p (A 1) + p (A 2) + ... + p (A n) \u003d p * (A 1) + p * (A 2) + ... + p * (A n)

Existujú rôzne typy grafov, pre ktoré majú stupne vrcholov niektoré špeciálne vlastnosti. Gróf sa volá homogénne, ak sa stupne všetkých jeho vrcholov rovnajú rovnakému číslu r: pre každý vrchol A:

p(A) = p* (A) = r

Cvičenie

Zostrojte homogénne orientované grafy stupňa r = 2 s n = 2,6,7,8 vrcholmi.

VZŤAHY.

Vzťahy a grafy.

Akýkoľvek matematický systém sa zaoberá súborom nejakých objektov alebo prvkov. (Znaky: algebra, geometria)

Na zostavenie matematickej teórie potrebujeme nielen tieto prvky samotné, ale aj vzťahy medzi nimi. (Príklady: pre čísla a > b; v geometrii - rovnosť trojuholníkov, // čiar; v teórii množín - rovnosť a inklúzie množín.)

Všetky tieto vzťahy sa týkajú dvoch objektov, preto sa nazývajú binárne vzťahy, alebo jednoducho vzťahy, existujú aj iné typy vzťahov, napr ternárne vzťahy týkajúci sa troch predmetov. (Napríklad bod A leží medzi bodmi B a C).

Uveďme všeobecnú definíciu binárneho vzťahu R: аRв - в je vo vzťahu k R k a.

Napríklad vzťah a > b znamená, že b patrí do množiny všetkých čísel menších ako a

V skutočnosti každý orientovaný graf G definuje nejaký vzťah v množine svojich vrcholov. Tento pomer možno zapísať ako: аGв. Znamená to, že graf má orientovanú hranu idúcu od a do b.

Špeciálne podmienky.

Nech je daný nejaký vzťah R. Ak je prvok a vo vzťahu R sám so sebou, potom zodpovedá slučke v grafe

Vzťah R, pre ktorý je splnená podmienka аRв pre akékoľvek a, sa volá reflexné.

Ak podmienka aRv nie je splnená pre žiadny prvok, potom sa volá R antireflexný postoj.V tomto prípade žiadny z vrcholov grafu nemá slučku.

Pre každý vzťah R možno definovať obrátený pomer R*, za predpokladu, že аR * в vtedy a len vtedy, ak аRв.

Z definície inverzného vzťahu je vidieť, že ak má graf G zodpovedajúci R hranu (a, b), potom graf G * zodpovedajúci R * musí mať hranu (c, a). Inými slovami, graf G * je inverzný k G, t.j. graf s rovnakými hranami ako G, ale opačne orientovaný.

Vzťah sa nazýva symetrické, ak z аRв nasleduje вРа.

Symetrický vzťah zodpovedá grafu s neorientovanými hranami; naopak, graf s neorientovanými hranami definuje nejaký symetrický vzťah.

Vzťah sa nazýva antisymetrický, ak z аRв vyplýva, že v Rа určite neplatí. Antisymetrické grafy vzťahov nemajú neorientované alebo opačne orientované hrany spájajúce rovnakú dvojicu vrcholov; navyše na nich nie sú žiadne slučky, t.j. tieto vzťahy sú antireflexívne.

pomer tranzitívne, ak z dvoch podmienok aRb a bRc vyplýva, že aRc.

Graf tranzitívneho vzťahu má nasledujúcu charakteristickú vlastnosť: pre každú dvojicu hrán (a, b), (b, c) existuje zatváranie hrana. Opakovaným aplikovaním tejto vlastnosti sme dospeli k záveru, že ak má tento graf smerovanú cestu z vrcholu X do vrcholu Y, potom existuje aj smerovaná hrana (x, y).

Predpokladajme, že existuje graf G s orientovanými hranami, ktorý nie je tranzitívny. Vo všetkých prípadoch môže byť smerovaný graf G prechodný pridaním smerovaných hrán, kým sa nepripojí uzáver pre každý pár jeho po sebe idúcich hrán. Takto získaný nový graf G m sa nazýva tranzitívny uzáver gróf G.

Vzťahy ekvivalencie.

Vzťah ekvivalencie, zvyčajne označovaný ~, má tieto tri vlastnosti:

jeden). Reflexivita: a ~ a;

2). Symetria: od a ~ po z po ~ a;

3). Tranzitivita: z a ~ do a do ~ c Þ a ~ c.

V skutočnosti je vzťah ekvivalencie zovšeobecnením vlastnosti rovnosti.

Vzťah ekvivalencie zavádza rozdelenie do množiny vrcholov triedy disjunktnej ekvivalencie.

Nech B i je množina vrcholov grafu ekvivalencie G, ktoré sú ekvivalentné vrcholu i. Potom sú všetky vrcholy patriace do B i spojené hranami, t.j. V i - kompletný graf G i . Na každom vrchole takéhoto grafu je slučka.Graf G sa rozdelí na množinu spojených komponentov G i .

Čiastočná objednávka.

Postoj čiastočná objednávka je (na príklade množín):

jeden). Reflexivita: A Ê A

2). Prechodnosť: ak A Ê B a B Ê C Þ A Ê C

3). Identita: ak A Ê B a B Ê Az A = B

Prísne inkluzívne vzťahy -

jeden). Antireflexivita: A ÉA sa nikdy nekoná;

2). Tranzitivita: ak A É B a B É C, potom A É C

Objednávkový vzťah(v presnom slova zmysle) sa nazýva striktné usporiadanie, a > b, pre ktoré okrem predchádzajúcich podmienok platí aj toto:

podmienka úplnosti. Pre akékoľvek dva nezhodné prvky v a a je vždy splnený jeden z dvoch vzťahov a>b alebo b>a.

Čiastočne usporiadaný graf sa zvyčajne zobrazuje v usporiadanej forme. Keďže pre všetky hrany (a, b) a (b, c) existuje uzatváracia hrana (a, c), možno ju vynechať.

PLOCHÉ GRAFY.

Podmienky pre rovinné grafy.

Gróf Kuratovský K 3.3

Grafický problém o troch domoch a troch studniach

Gróf Kuratovský K 5

Tieto dva grafy NIE SÚ PLOCHÉ!

Rozšírenie grafu- na niektoré hrany boli umiestnené nové vrcholy, teda tieto hrany

sa stali elementárnymi reťazcami pozostávajúcimi z niekoľkých hrán.

Obrátená prevádzka, v ktorom sú oddeľujúce vrcholy odstránené z elementárnych reťazcov, sa nazýva kompresia graf.

Kuratovského veta

Aby bol graf plochý, je potrebné a postačujúce, aby v sebe neobsahoval žiadny graf, ktorý by sa dal skomprimovať na graf K 3,3 alebo K 5.

Eulerov vzorec

Budeme uvažovať o rovinných grafoch, ktoré sa tvoria v rovine polygonálne siete. to znamená, že okraje rovinného grafu G tvoria množinu polygónov priľahlých k sebe, rozdeľujúcich rovinu na polygonálne oblasti.

Z definície polygonálnych grafov vyplýva, že sú spojené. Tiež požadujeme, aby žiadny polygón neležal vo vnútri iného. Hraničné hrany každého takéhoto mnohouholníka tvoria cyklus, niekedy tzv minimálny cyklus. Časť roviny uzavretá v polygóne sa nazýva tvár grafu. Graf má tiež maximálny cyklus C 1, ktorý obklopuje celý graf so všetkými jeho plochami. Časť roviny ležiacu mimo C 1 budeme považovať aj za plochu grafu s hranicou C 1 - nekonečné tvár F ¥ .

Označiť podľa

počet vrcholov, hrán a plôch priestorový polygón..

Eulerova veta

c - p + r = 2

dôkaz: Vzorec je zrejmý pre mnohouholník s n hranami. Skutočne, n vrcholov a n hrán, ako aj dve steny F 1 F ¥

Do grafu s r plochami pridáme novú plochu tak, že pozdĺž plochy F ¥ nakreslíme nejaký elementárny reťazec spájajúci dva vrcholy maximálneho grafu G. Ak má tento oblúk r hrán, musíme pridať r - 1 nový vrchol a jeden nový tvár. Ale potom

c' - p' + r' = (c + r - 1) - (p + r) + (r + 1) = c - p + r (= 2!)

indukčnou hypotézou.

Maticové reprezentácie.

1. Matica incidentov A.

a). Pre neorientovaný graf matica výskytu je matica, ktorej riadky zodpovedajú vrcholom a ktorej stĺpce zodpovedajú hranám. Prvok matice sa rovná 1, ak vrchol dopadá na hranu. V opačnom prípade má prvok matice hodnotu 0.

b). Pre orientovaný graf je prvok matice dopadu +1, keď vrchol dopadajúci na oblúk je počiatočným vrcholom oblúka (t. j. oblúk pochádza z tohto vrcholu). Prvok je -1, keď oblúk vstúpi do vrcholu. Ak vrchol nespadá do oblúka, potom je prvok matice 0.

2. Matica cyklov C.

a). V prípade neorientovaného grafu riadky matice cyklu zodpovedajú jednoduchým cyklom grafu a stĺpce zodpovedajú jeho okrajom. Maticový prvok a ij =1, ak cyklus С i obsahuje hranu e j . V opačnom prípade a ij = 0.

b). Pre orientovaný graf a ij =1, -1 alebo 0 v závislosti od toho, či orientácia cyklu C i a oblúka e j je rovnaká alebo opačná, alebo tento cyklus oblúk e j vôbec neobsahuje.

3. Matica susednosti vrcholov (alebo jednoducho matica susednosti) V je matica, ktorej riadky a stĺpce zodpovedajú vrcholom a prvok matice a ij v prípade neorientovaného grafu sa rovná počtu hrán spájajúcich vrcholy i a j. . Pre orientovaný graf sa prvok a ij rovná počtu hrán smerujúcich z vrcholu i do vrcholu j.

Onovye vety týkajúce sa maticového znázornenia grafov.

1. Poradie (maximálny počet lineárne nezávislých stĺpcov) matice výskytu A spojeného grafu (riadeného a neorientovaného) s n vrcholmi je rovné (n-1).

2). Hodnosť matice cyklu C súvislého grafu s m hranami a n vrcholmi je (m-n+1).

Príklad použitia matice susednosti.

Nasledujúce zobrazenie ukazuje, že grafy G 1 a G 2 sú izomorfné

V susedných maticách sú riadky a stĺpce súčasne permutované, čo možno vykonať pomocou transformácie podobnosti a permutačnej matice.

A 2 \u003d PA 1 P", kde

P = alebo p ij =d p(i),j (Kroneckerov symbol)

a P" je transponovaná matica.

Nájdenie matice P môže byť zložité.

Izomorfizmus G 1 a G 2 znamená, že A 1 a A 2 majú rovnaké vlastné hodnoty. Táto podmienka však nestačí (príklad nižšie).