Příklady digrafu. Definice orientovaného grafu

Typy grafů mohou být určeny obecnými principy jejich konstrukce (například bipartitní graf a eulerovský graf), nebo mohou záviset na určitých vlastnostech vrcholů nebo hran (například orientovaný a neorientovaný graf, obyčejný graf). graf).

Orientované a neorientované grafy

Odkazy(pořadí dvou konců hrany grafu není podstatné). neorientovaný .

Grafy, ve kterých jsou všechny hrany oblouky(pořadí dvou konců hrany grafu je významné). orientované grafy nebo digrafy .

Neorientovaný graf lze prezentovat ve formě orientovaný graf , pokud je každý z jeho článků nahrazen dvěma oblouky s opačnými směry.

Smyčkové grafy, smíšené grafy, prázdné grafy, multigrafy, běžné grafy, kompletní grafy

Pokud graf obsahuje smyčky, pak je tato okolnost speciálně stanovena přidáním slov „se smyčkami“ k hlavním charakteristikám grafu, například „digraf se smyčkami“. Pokud graf neobsahuje smyčky, jsou přidána slova „žádné smyčky“.

Smíšený je graf, který obsahuje hrany alespoň dvou ze tří uvedených typů (linky, oblouky, smyčky).

Graf sestávající pouze z holé vrcholy, volal prázdný .

Multigraf je graf, ve kterém mohou být dvojice vrcholů spojeny více hranami, tedy obsahujícími více hran, ale neobsahující smyčky.

Nazývá se graf bez oblouků (tedy neorientovaný), bez smyček a více hran obyčejný . Obyčejný graf je znázorněn na obrázku níže.

Zavolá se graf daného typu kompletní , pokud obsahuje všechny hrany možné pro tento typ (s konstantní množinou vrcholů). V úplném běžném grafu je tedy každá dvojice odlišných vrcholů spojena právě jednou spojnicí (obrázek níže).

Bipartitní graf

Graf se nazývá bipartitní , lze-li množinu jeho vrcholů rozdělit na dvě podmnožiny tak, že žádná hrana nespojuje vrcholy téže podmnožiny.

Příklad 1. Stavět plný bipartitní graf.

Kompletní bipartitní graf se skládá ze dvou množin vrcholů a všech možných vazeb spojujících vrcholy jedné množiny s vrcholy jiné množiny (obrázek níže).

Eulerův graf

Už jsme se dotkli problémy s Königsbergskými mosty. Eulerovo negativní řešení tohoto problému vedlo k první publikované práci o teorii grafů. Problém přechodu mostu lze zobecnit na následující problém teorie grafů: Je možné v daném grafu najít cyklus, který obsahuje všechny vrcholy a všechny hrany? Graf, ve kterém je to možné, se nazývá eulerovský graf.

Tak, Eulerův graf je graf, ve kterém můžete projet všechny vrcholy a zároveň jednu hranu pouze jednou. V něm musí mít každý vrchol pouze sudý počet hran.

Příklad 2 Je úplný graf se stejným číslem n hrany, ke kterým je každý vrchol incidentní, eulerovský graf? Vysvětlete odpověď. Dát příklad.

Odpovědět. Li n je liché číslo, pak je každý vrchol incidentní n-1 žebra. V tomto případě je daný graf eulerovský graf. Příklady takových grafů jsou uvedeny na obrázku níže.

Běžný graf

Pravidelné počítání je souvislý graf, kde všechny vrcholy mají stejný stupeň k. Obrázek 2 tedy ukazuje příklady pravidelných grafů, nazývaných 4-pravidelné a 2-pravidelné grafy nebo pravidelné grafy 4. stupně a 2. stupně podle stupně jejich vrcholů.

Počet vrcholů v běžném grafu k- stupeň nemůže být nižší k+1. Běžný graf lichého stupně může mít pouze sudý počet vrcholů.

Příklad 3 Sestrojte pravidelný graf, ve kterém má nejkratší cyklus délku 4.

Řešení. Uvažujeme takto: aby délka cyklu splnila danou podmínku, je nutné, aby počet vrcholů v grafu byl násobkem čtyř. Pokud je počet vrcholů čtyři, dostanete graf zobrazený na obrázku níže. Je pravidelný, ale jeho nejkratší cyklus má délku 3.

Zvýšíme počet vrcholů na osm (další číslo je násobkem čtyř). Vrcholy spojíme hranami tak, aby se stupně vrcholů rovnaly třem. Získáme následující graf, který splňuje podmínky problému.

Hamilton hrabě

Hamilton hrabě je graf obsahující hamiltonovský cyklus. Hamiltonovský cyklus se nazývá jednoduchý cyklus procházející všemi vrcholy uvažovaného grafu. Zjednodušeně řečeno, hamiltonovský graf je graf, ve kterém lze procházet všemi vrcholy a každý vrchol se při průchodu opakuje pouze jednou. Příklad hamiltonovského grafu je na obrázku níže.

Příklad 4. Vzhledem k bipartitnímu grafu, ve kterém n- počet vrcholů z množiny A, A m- počet vrcholů z množiny B. V jakém případě se bude jednat o graf eulerovský a v jakém o hamiltonovský graf?

Než začnete studovat samotné algoritmy, musíte mít základní znalosti o samotných grafech a rozumět tomu, jak jsou reprezentovány v počítači. Zde nebudou podrobně popsány všechny aspekty teorie grafů (není to nutné), ale pouze ty, jejichž neznalost výrazně zkomplikuje asimilaci této oblasti programování.

Několik příkladů poskytne malý náčrt grafu. Typickým grafem je tedy mapa metra nebo nějaká jiná trasa. Programátor se vyzná zejména v počítačové síti, což je také graf. Společnou věcí je zde přítomnost bodů spojených čarami. Takže v počítačové síti jsou body jednotlivé servery a linky jsou různé typy elektrických signálů. V metru jsou první stanice, druhou tunely položené mezi nimi. V teorii grafů se nazývají body vrcholy (uzly) a řádky jsou žebra (oblouky). Tím pádem, graf je soubor vrcholů spojených hranami.

Matematika nepracuje s obsahem věcí, ale s jejich strukturou, abstrahuje ji od všeho, co je dáno jako celek. Přesně pomocí této techniky můžeme dojít k závěru, že některé objekty jsou grafy. A protože teorie grafů je součástí matematiky, není pro ni v zásadě žádný rozdíl, co je objekt; důležité je pouze to, zda se jedná o graf, tedy zda má vlastnosti požadované pro grafy. Proto před uvedením příkladů zvýrazňujeme v uvažovaném objektu jen to, co si myslíme, že nám umožní ukázat analogii, hledáme to, co je společné.

Vraťme se k počítačové síti. Má určitou topologii a může být konvenčně zobrazen ve formě určitého počtu počítačů a cest, které je spojují. Obrázek níže ukazuje jako příklad plně propojenou topologii.

Je to v podstatě graf. Těchto pět počítačů jsou vrcholy a spojení (cesty signálu) mezi nimi jsou hrany. Nahrazením počítačů vrcholy získáme matematický objekt – graf, který má 10 hran a 5 vrcholů. Vrcholy mohou být očíslovány jakýmkoli způsobem, a ne nutně tak, jak je znázorněno na obrázku. Stojí za zmínku, že tento příklad nepoužívá jedinou smyčku, tedy hranu, která opouští vrchol a okamžitě do něj vstupuje, ale smyčky se mohou vyskytovat v problémech.

Zde jsou některé důležité zápisy používané v teorii grafů:

• G=(V, E), zde G je graf, V jsou jeho vrcholy a E jsou jeho hrany;
• |V| – pořadí (počet vrcholů);
• |E| – velikost grafu (počet hran).

V našem případě (obr. 1) |V|=5, |E|=10;

Když je z jakéhokoli vrcholu přístupný jakýkoli jiný vrchol, pak se takový graf zavolá neorientovaný spojený graf (obr. 1). Pokud je graf připojen, ale tato podmínka není splněna, pak se takový graf zavolá orientované nebo digraf (obr. 2).

Orientované a neorientované grafy mají koncept vertexového stupně. Nejvyšší stupeň je počet hran, které jej spojují s jinými vrcholy. Součet všech stupňů grafu je roven dvojnásobku počtu všech jeho hran. Pro obrázek 2 je součet všech mocnin 20.

V digrafu, na rozdíl od neorientovaného grafu, je možné se pohybovat z vrcholu h do vrcholu s bez mezilehlých vrcholů, pouze když hrana opustí h a vstoupí do s, ale ne naopak.

Orientované grafy mají následující zápis:

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

Třetím typem grafů je smíšený grafy (obr. 3). Mají směrované i nesměrové hrany. Formálně se smíšený graf zapisuje takto: G=(V, E, A), kde každé z písmen v závorce znamená totéž, co mu bylo přiřazeno dříve.

V grafu na obrázku 3 jsou některé oblouky směrované [(e, a), (e, c), (a, b), (c, a), (d, b)], jiné jsou neorientované [(e, d), (e, b), (d, c)…].

Dva a více grafů se na první pohled může zdát odlišnou strukturou, což vzniká jejich rozdílným znázorněním. Ale není tomu tak vždy. Vezměme si dva grafy (obr. 4).

Jsou si navzájem ekvivalentní, protože bez změny struktury jednoho grafu můžete vytvořit další. Takovým grafům se říká izomorfní, tj. mající tu vlastnost, že jakýkoli vrchol s určitým počtem hran v jednom grafu má identický vrchol v jiném. Obrázek 4 ukazuje dva izomorfní grafy.

Když je každá hrana grafu spojena s určitou hodnotou, která se nazývá váha hrany, pak takový graf pozastaveno. V různých úlohách mohou jako váhy fungovat různé typy měření, například délky, ceny, trasy atd. V grafickém znázornění grafu jsou hodnoty hmotnosti zpravidla uvedeny vedle okrajů.

V kterémkoli z grafů, které jsme uvažovali, je možné vybrat cestu a navíc více než jednu. Cesta je posloupnost vrcholů, z nichž každý je připojen k následujícímu hranou. Pokud se první a poslední vrchol shodují, pak se taková cesta nazývá cyklus. Délka cesty je určena počtem hran, které ji tvoří. Například na obrázku 4.a je cesta sekvence [(e), (a), (b), (c)]. Tato cesta je podgrafem, protože se na ni vztahuje definice toho druhého, a to: graf G'=(V', E') je podgrafem grafu G=(V, E) pouze tehdy, když V' a E' patří V, E .

V první lekci, při zavádění pojmu graf, jsme se jako příklad podívali na soutěže mezi sportovními týmy. My. spojil dva týmy, řekněme A a C, s hranou AC v případě, že tyto týmy již hrály mezi sebou. Takový graf však neodpovídá na jednu velmi důležitou otázku: kdo přesně vyhrál hru?
Tento nedostatek lze snadno odstranit. Pokud tým A porazí C, souhlasíme s umístěním šipky na hranu AC, směřující z A do C. Předpokládejme, že známe výsledky všech již odehraných her, a přidáme Obr. 1 odpovídající šipky; Nechť to vyústí v graf znázorněný na obr. 58.

Obrázek 58.

Tento graf ukazuje, že tým A vyhrál proti C, tým F prohrál s A a B vyhrál všechny zápasy – s C, E, F atd.

Okraj se nazývá graf orientované, pokud je uvažován jeden vrchol začátek žebra, a ostatní - konec.
Nazýváme graf, jehož hrany jsou všechny orientované orientacegraf.
Stejný vrchol orientovaného grafu může sloužit jako začátek pro některé hrany a konec pro jiné. Podle toho se rozlišují dva stupně vrcholu: výstupní stupeň a vstupní stupeň.
Výnosnost vrcholu A orientovaného grafu je počet hran vycházejících z A (zápis: d+(A)).
Vstupní stupeň vrcholu A orientovaného grafu je počet prvků v Ažebra (označení: d-(A)).
Co když některá hra skončí remízou? Výsledky kreslení můžeme promítnout do grafu tak, že odpovídající hrany ponecháme bez orientace. V tomto případě dostaneme tzv smestinný počet, která má orientované i neorientované okraje.
Cesta v orientovaném grafu G od A1 do An je posloupnost orientovaných hran<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, takže konec každé předchozí hrany se shoduje se začátkem následující a žádná hrana se nevyskytuje více než jednou.

Rýže. 59
Pokud v orientovaném grafu G existuje cesta z A do B, pak zpáteční cesta z V Na A nemusí být (obr. 59).
Pokud existuje směrovaná cesta z A do B, pak se říká, že B je dosáhnoutma od A,
Ve sloupci G na obrázku je dosažitelné 38 V
z A, A není dosažitelné z B.
Jednoduchý způsob v orientovaném grafu se nazývá cesta, ve které není žádný vrchol obsažen více než jednou. Uzavřená cesta v orientovaném grafu se nazývá řízený cyklus.
Délka cesty počet hran v této cestě se nazývá.
Vzdálenost z A do B v orientovaném grafu je délka nejkratší cesty z A do B. Pokud z A do B žádná cesta nevede, pak se vzdálenost z A do B nazývá nekonečná a značí se ?. Vzdálenost z A do B budeme označovat jako S (AB). Pro graf na obrázku 38
S (AB) = 1, S (CB) - 2, S (BC) = ?.
Problém 9.1.
V přímořském letovisku se po zavedení jednosměrného provozu ukázalo, že počet ulic, po kterých můžete vjet do každé křižovatky, se rovná počtu ulic, po kterých ji můžete opustit. Dokažte, že je možné navrhnout obchůzkovou trasu, která začíná a končí na stejném místě a prochází každým úsekem ulice právě jednou.
Řešení.
Sestrojme digraf G, který definuje pohyb ve městě.
Digraf se nazývá koherentní, jestliže z kteréhokoli z jeho vrcholů do kteréhokoli jiného lze jít po obloucích bez ohledu na jejich orientaci. Souvislý digraf se nazývá Euler, pokud má eulerovský cyklus.
Věta 12. Souvislý digraf je eulerovský právě tehdy, když pro každý z jeho vrcholůprotiplatí rovnostd- (proti) = d+ (proti) .
Věta je dokázána přesně stejným způsobem jako věta v Úloze 4.2.
Z podmínek úlohy vyplývá, že pro vrcholy sestrojeného grafu G platí rovnost d-(v) = d+(v). V důsledku toho eulerovský graf G a eulerovský cyklus určí požadovanou trasu obchůzky.
Problém 9.2.
Na rovině je vyznačen konečný počet bodů. Některé dvojice bodů jsou počátky a konce vektorů a počet vektorů vstupujících do kteréhokoli bodu se rovná počtu vektorů, které jej opouštějí. Najděte součet vektorů.
Řešení.
Body roviny spolu s vektory tvoří digraf G. Cyklus digrafu, jehož všechny vrcholy jsou různé, se nazývá obrys.
Věta 13. Souvislý digrafGEulers tehdy a jen tehdyGje spojení vrstevnic, které po párech nemají společné hrany.
Důkaz. Nezbytnost Nechť G je eulerovský digraf. Zvažte jeho libovolný vrchol u1. Ponechme vrchol u1 podél nějakého oblouku (u1, u2), což lze udělat, protože digraf G je souvislý. Protože d-(u2) = d+(u2), pak můžeme vystoupit z vrcholu u2 po oblouku (u2, u3) . Digraf G má konečný počet vrcholů, takže nakonec skončíme na nějakém vrcholu w, kde jsme byli předtím. Část řetězce, která začíná a končí ve vrcholu w, je obrys C1. Odeberme oblouky obrysu C1 z digrafu G . Ve výsledném digrafu G1 (případně rozpojeném) se vstupní a výstupní stupně vrcholů patřících do C snížily o jednu, vstupní a výstupní stupně zbývajících vrcholů se nezměnily. Pro libovolný vrchol v digrafu C1 tedy bude platit rovnost d-(v) = d+(v). Proto v digrafu G1 můžeme vybrat obrys C 2 atd.
Dostatečnost se dokazuje spojením vrstevnic do eulerovského cyklu (viz důkaz věty v Úloze 4.2).
Věta byla prokázána. Je možné, že digraf G definující vektory v naší úloze spolu nesouvisí. Aplikováním osvědčené věty na každou spojenou část digrafu získáme rozdělení vektorů do vrstevnic. Součet vektorů patřících k jednomu obrysu je roven nule. Proto je součet všech vektorů nulový.

Orientovaný graf(Krátce digraf) - (více) graf, jehož hranám je přiřazen směr. Řízené hrany se také nazývají oblouky a v některých zdrojích jen žebra. Graf, ve kterém není žádné hraně přiřazen směr, se nazývá neorientovaný graf resp nedigraf.

Základní pojmy

Formálně, digraf D = (V, E) (\displaystyle D=(V,E)) se skládá z mnoha V (\displaystyle V), jehož prvky se nazývají vrcholy a sady E (\displaystyle E) uspořádané dvojice vrcholů u , v ∈ V (\displaystyle u,v\in V).

Oblouk (u, v) (\displaystyle (u,v)) vedlejší vrcholy u (\displaystyle u) A v (\displaystyle v). Zároveň to říkají u (\displaystyle u) - počáteční vrchol oblouky a v (\displaystyle v) - konečný vrchol.

Konektivita

Trasa v digrafu je střídající se posloupnost vrcholů a oblouk, typ v 0 ( v 0 , v 1 ) v 1 ( v 1 , v 2 ) v 2 . . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(vrcholy se mohou opakovat). Délka trasy- počet oblouků v něm.

Cesta Tady je trasa v digrafu bez opakujících se oblouků, snadný způsob- žádné opakující se vrcholy. Pokud existuje cesta z jednoho vrcholu do druhého, pak druhý vrchol dosažitelný od prvního.

Obvod je tam uzavřený cesta.

Pro poloviční trasa omezení směru oblouků je odstraněno a na půli cesty A poloviční obvod.

Digraph vysoce koherentní, nebo jednoduše silný, pokud jsou všechny jeho vrcholy vzájemné dosažitelný; jednosměrně připojeno, nebo jednoduše jednostranný, je-li pro libovolné dva vrcholy alespoň jeden dosažitelný z druhého; volně spojené, nebo jednoduše slabý, pokud ignorování směru oblouků vytvoří souvislý (multi)graf;

Maximum silný podgraf se nazývá silná složka; jednostranný komponent A slabá složka jsou definovány podobně.

Kondenzace digraf D (\displaystyle D) nazývá se digraf, jehož vrcholy jsou silnými komponentami D (\displaystyle D) a oblouk dovnitř D ⋆ (\displaystyle D^(\star )) ukazuje přítomnost alespoň jednoho oblouku mezi vrcholy obsaženými v odpovídajících komponentách.

Další definice

Orientovaný acyklický graf nebo houpací sít existuje nekonturový digraf.

Orientovaný graf získaný z daného pomocí změny směru hran na opačný se nazývá zvrátit.

Obraz a vlastnosti všech digrafů se třemi uzly

Legenda: S- slabý, OS- jednostranný, SS- silný, N- je orientovaný graf, G- je houpací síť (acyklická), T- je turnaj

0 oblouků	1 oblouk	2 oblouky	3 oblouky	4 oblouky	5 oblouků	6 oblouků
prázdné, N, G	N, G		OS	CC	CC	plný, CC
		OS, N, G	CC, N, T	CC
		C, N, G	OS, N, G, T	OS
		C, N, G	OS

Hrana je uspořádaná dvojice vrcholů. Nazýváme graf, u kterého je naznačen směr každé jeho hrany orientované.

Pochopitelně aplikace na turnaje. Například šipka jde od poraženého týmu k vítěznému, takže orientovaný graf ukazuje nejen kdo s kým hrál, ale také kdo vyhrál.

Můžete také definovat následující nebo preferenční vztahy s orientovanými grafy.

Například, v grafech algoritmů vrcholy grafu odpovídají prováděná operace a oblouky (orientované hrany) odpovídají datové závislosti(tj. jaká vstupní data jsou potřebná k provedení operace).

Například při komplexním vyhodnocování vzorků (například v geologii) ukazuje směr hrany přednost. V normálním preferenčním systému by neměly být žádné cykly

Tanya Natasha

abyste si vždy mohli vybrat, jinak je nutné přehodnotit systém preferencí.

Jednosměrný.

Silniční mapa s pokyny pro jízdu poskytuje speciální příklady orientovaných grafů. Abychom se vypořádali s obousměrnými cestami, zavedeme místo jedné silnice (nebo místo jedné neorientované hrany) dvě orientované hrany spojující stejné vrcholy a mající opačné směry.

Otázkou je, za jakých podmínek lze ulice města orientovat tak, aby se dalo přejet z kteréhokoli bodu do kteréhokoli jiného, ​​aniž by došlo k porušení pravidel silničního provozu v ulicích.

V jazyce teorie grafů je to formulováno následovně: za jaké podmínky mohou být hrany grafu G orientovány tak, aby pro libovolnou dvojici jeho vrcholů existoval orientovaný řetězec, který je spojuje?

Je jasné, že každý takový graf musí být propojen, ale to nestačí.

Bude volána hrana E = (A,B). spojovací žebro nebo šíje, pokud je to jediná cesta z A do B (nebo naopak).

Spojovací hrana rozděluje všechny vrcholy grafu na dvě množiny: ty, které lze dosáhnout z A, aniž bychom procházeli podél hrany E, a ty, které lze dosáhnout z B, aniž bychom procházeli podél E. Graf se v tomto případě skládá ze dvou částí G 1 a G 2 spojeny pouze hranou E (obr. a a a+1).

Na mapě města je spojovací hrana jedinou dálnicí spojující jednotlivé části města. Je jasné, že pokud by taková dálnice měla jednosměrný provoz, tak by nebyl průjezd z jedné části města do druhé.

Pokud se hrana E i = (A i, B i) nespojuje, pak existuje další cesta spojující A i a B i a neprocházející podél E i. Proto takové hraně budeme říkat cyklická hrana.

Obr.2 Vazba Obr. 2+1 Final (linking) Obr. 2+2 Cykl

žebro žebro

Věta 1 Li G- neorientovaný souvislý graf, pak je vždy možné orientovat cyklické hrany z G , přičemž spojovací hrany ponecháme neorientované, takže libovolný pár vrcholů v tomto grafu může být spojen směrovanou cestou.

Pro územní plán města lze toto tvrzení formulovat následovně: je-li obousměrný provoz ponechán pouze na mostech (za předpokladu, že tento most je jediným mostem přes řeku) a na slepých uličkách, pak na všech ostatních ulicích je provoz jednosměrný. lze zřídit tak, aby doprava zajišťovala komunikaci všech částí města.

Tuto větu můžeme dokázat určením způsobu, jak vhodně orientovat graf. Pojďme si vybrat G libovolný okraj E = (A,B) . Li E - spojovací hrana, zůstane oboustranná a pak bude možné od ní přecházet A Na V a naopak (obr. 2+3).

obr.2+3 Obr. 2+4

Li E je cyklická hrana, pak je zařazena do nějakého cyklu S, na kterém lze nastavit cyklickou orientaci (obr. 2+4).

Předpokládejme, že jsme již nějakou část orientovali N graf G, takže z libovolného vrcholu grafu N můžete přejít do kteréhokoli jiného jeho vrcholu a dodržovat pravidla jednosměrného provozu. Od grafu G je připojen, pak buď N odpovídá celému grafu G, nebo je tam hrana E= (A,B), která nepatří N , ale jeden z jeho vrcholů, řekněme A , patří N .

Li E - spojovací žebro AB , pak zůstane oboustranný. Pak pro jakýkoli vrchol X graf N můžete najít orientovaný řetězec R , připojení X s A , což znamená (přes okraj E ), a s V . Zpátky shora V přes okraj E Můžeš jít do A a poté podél přibližného řetězce Z - z A Na X (Obrázek a+5). Připojování E Na H , dostaneme již většinu grafu G , mající požadované vlastnosti. Pokud okraj E= (A,B) je cyklický, patří do nějakého cyklu S . Nastavili jsme směr S z A před V a dále S k prvnímu vrcholu D z S ve vlastnictví N (obr. a+6).

rýže. a+5 Obr. a+6

Všechny tyto okraje připevníme k N . Nechat X - libovolný vrchol z N , A U - libovolný vrchol z S ; můžete najít orientovaný řetězec R , patřící N a připojení X S A a pak spolu S jít na vrchol U z S . Zpět z U můžete jít spolu S na vrchol D , a z toho - sounáležitosti N orientovaný řetězec Z - z D Na X . Proto orientovaný graf získaný přidáním do N specifikované okraje smyčky S , rovněž splňuje požadované podmínky. Pokračujeme-li v tomto procesu, nakonec původní graf orientujeme požadovaným způsobem G .

Stupně vrcholů.

Pro orientované grafy máme v každém vrcholu počet p(A) odchozích hran a počet p * (A) příchozích hran. Celkový počet hran je:

N = p(A 1) + p(A 2) +... + p(A n) = p * (A 1)+p * (A 2)+...+p * (A n)

Existují různé typy grafů, pro které mají stupně vrcholů některé speciální vlastnosti. Graf se nazývá homogenní, jestliže se stupně všech jeho vrcholů rovnají stejnému číslu r: pro každý vrchol A:

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

Cvičení

Sestrojte homogenní orientované grafy stupně r = 2 s počtem vrcholů n = 2,6,7,8.

VZTAH.

Vztahy a grafy.

Každý matematický systém se zabývá množstvím nějakých objektů nebo prvků. (Znaky: algebra, geometrie)

Abychom mohli sestavit matematickou teorii, potřebujeme nejen tyto prvky samotné, ale také vztah mezi nimi. (Příklady: pro čísla a > b; v geometrii - rovnost trojúhelníků, // přímky; v teorii množin - rovnost a zahrnutí množin.)

Všechny tyto vztahy se týkají dvou objektů, proto se jim říká binární vztahy, nebo jednoduše vztahy, existují například další typy vztahů ternární vztahy, týkající se tří objektů. (Například bod A leží mezi body B a C).

Uveďme obecnou definici binární relace R: аRв - в je ve vztahu R k а.

Například vztah a > b znamená, že b patří do množiny všech čísel menších než a

Ve skutečnosti každý orientovaný graf G definuje nějakou relaci ve své vrcholové množině. Tento vztah lze zapsat ve tvaru: аGв. To znamená, že graf má orientovanou hranu od a do b.

Zvláštní podmínky.

Nechť je dána nějaká relace R. Je-li prvek a ve vztahu R sám se sebou, pak odpovídá smyčce v grafu

Vztah R, pro který je splněna podmínka аRв pro jakékoli a, volal reflexní.

Pokud podmínka аRв není splněna pro žádný prvek, zavolá se R antireflexní postoj.V tomto případě nemá ani jeden vrchol grafu smyčku.

Pro každý vztah R můžeme definovat obrácený poměr R*, uvážíme-li, že aR * v právě tehdy, když aR v.

Z definice inverzního vztahu je zřejmé, že pokud má graf G odpovídající R hranu (a, b), pak graf G * odpovídající R * musí mít hranu (b, a). Jinými slovy, graf G * je inverzní k G, tzn. graf se stejnými hranami jako G, ale opačně orientovanými.

Vztah se nazývá symetrický, jestliže aRb implikuje bRa.

Symetrický vztah odpovídá grafu s neorientovanými hranami; naopak, graf s neorientovanými hranami definuje nějaký symetrický vztah.

Vztah se nazývá antisymetrický, pokud z аRв vyplývá, že se zjevně neodehrává v Rа. Antisymetrické grafy vztahů nemají neorientované nebo opačně orientované hrany spojující stejnou dvojici vrcholů; navíc na nich nejsou smyčky, tzn. tyto vztahy jsou antireflexní.

Poměr tranzitivně, jestliže ze dvou podmínek аRв a вRс vyplývá, že аRc.

Tranzitivní relační graf má následující charakteristickou vlastnost: pro každou dvojici hran (a, b), (b, c) existuje koncové okraj. Opakovaným aplikováním této vlastnosti dojdeme k závěru, že pokud na tomto grafu existuje orientovaná cesta vedoucí z vrcholu X do vrcholu Y, pak existuje i orientovaná hrana (x, y).

Předpokládejme, že existuje graf G s orientovanými hranami, který není tranzitivní. Ve všech případech může být směrovaný graf G tranzitivní přidáním směrovaných hran k němu, dokud není připojen uzávěr pro každý pár jeho následných hran. Takto získaný nový graf G m se nazývá tranzitivní uzávěr sloupec G.

Ekvivalenční vztahy.

Relace ekvivalence, obvykle označovaná symbolem ~, je charakterizována následujícími třemi vlastnostmi:

1). Reflexivita: a ~ a;

2). Symetrie: od ~ do Þ do ~ a;

3). Tranzitivita: od a ~ do a v ~ c Þ a ~ c.

Ve skutečnosti je vztah ekvivalence zobecněním vlastnosti rovnosti.

Vztah ekvivalence zavádí rozdělení do množiny vrcholů třídy disjunktní ekvivalence.

Nechť B i je množina vrcholů grafu ekvivalence G ekvivalentní vrcholu i. Pak jsou všechny vrcholy patřící do B i navzájem spojeny hranami, tzn. V i je úplný graf G i. V každém vrcholu takového grafu je smyčka, graf G se rozdělí na množinu spojených komponent G i .

Částečná objednávka.

přístup dílčí objednávka- toto (na příkladu množin):

1). Reflexivita: A Ê A

2). Transitivita: pokud A Ê B a B Ê C Þ A Ê C

3). Identita: pokud A Ê B a B Ê AÞ A = B

Přísné inkluzní vztahy -

1). Antireflexivita: A ÉA se nikdy nekoná;

2). Tranzitivita: pokud A É B a B É C, pak A É C

Objednávkový vztah(v užším slova smyslu) se nazývá přísné uspořádání, a>b, pro které kromě předchozích podmínek platí také:

Podmínka úplnosti. Pro libovolné dva neshodné prvky b a a je vždy splněn jeden ze dvou vztahů a>b nebo b>a.

Částečný graf řazení je obvykle zobrazen v uspořádané formě. Protože pro všechny hrany (a, b) a (b, c) existuje uzavírací hrana (a, c), lze ji vynechat.

PLOCHÉ GRAFY.

Podmínky pro rovinné grafy.

Kuratovského graf K 3.3

Grafický problém tří domů a tří studní

Kuratovský hrabě K 5

Tyto dva grafy NEJSOU PLOCHÉ!

Rozšíření grafu- na některé hrany byly umístěny nové vrcholy, tedy tyto hrany

se staly elementárními řetězci skládajícími se z několika hran.

Reverzní provoz, ve kterém jsou oddělující vrcholy odstraněny z elementárních řetězců, se nazývá komprese graf.

Kuratowského teorém

Aby byl graf plochý, je nutné a postačující, aby v sobě neobsahoval žádný graf, který by se dal zkomprimovat do grafu K 3,3 nebo grafu K 5.

EULEROVA FORMULE

Budeme uvažovat rovinné grafy, které se tvoří na rovině polygonální sítě. To znamená, že hrany rovinného grafu G tvoří množinu vzájemně sousedících polygonů, které rozdělují rovinu na polygonální oblasti.

Z definice polygonálních grafů vyplývá, že jsou propojené. Požadujeme také, aby žádný polygon neležel uvnitř jiného. Hrany hranic každého takového mnohoúhelníku tvoří cyklus, někdy nazývaný minimální cyklus. Část roviny obsažená v polygonu se nazývá okraj grafu. Graf také obsahuje maximální cyklus C1, obklopující celý graf se všemi jeho plochami. Část roviny ležící mimo C 1 budeme uvažovat také jako plochu grafu s hranicí C 1 - nekonečný tvář F ¥ .

Označme podle

počet vrcholů, hran a ploch prostorový polygon..

Eulerova věta

c - p + g = 2

Důkaz: Vzorec je zřejmý pro mnohoúhelník s n hranami. Ve skutečnosti, n vrcholů a n hran, stejně jako dvě plochy F 1 F ¥

Do grafu s r hranami přidáme novou hranu, nakreslíme podél plochy F ¥ nějaký elementární řetězec spojující dva vrcholy maximálního grafu G. Pokud má tento oblouk r hran, pak budeme muset přidat r - 1 nový vrchol a jeden nový okraj. Ale pak

c’ - p’ + g’ = (c + g - 1) - (p + g) + (g + 1) = c - p + g (=2!)

podle indukční hypotézy.

Maticové reprezentace.

1. Matice incidentů A.

A). Pro neorientovaný graf matice incidentů je matice, jejíž řádky odpovídají vrcholům a sloupce hranám. Prvek matice je roven 1, pokud vrchol dopadá na hranu. V opačném případě má prvek matice hodnotu 0.

b). U orientovaného grafu je prvek matice dopadu +1, když je vrchol dopadající na oblouk počátečním vrcholem oblouku (tj. oblouk vychází z tohoto vrcholu). Prvek je -1, když oblouk vstupuje do vrcholu. Pokud vrchol nespadá do oblouku, pak je prvek matice 0.

2. Matice cyklů C.

A). U neorientovaného grafu odpovídají řádky matice cyklu jednoduchým cyklům grafu a sloupce jeho okrajům. Maticový prvek a ij =1, pokud cyklus C i obsahuje hranu e j . Jinak a ij =0.

b). Pro orientovaný graf a ij =1, -1 nebo 0 podle toho, zda je orientace cyklu C i a oblouku e j stejná nebo opačná, nebo zda daný cyklus oblouk e j vůbec neobsahuje.

3. Matice sousednosti vrcholů (nebo jednoduše matice sousednosti) V je matice, jejíž řádky a sloupce odpovídají vrcholům a prvek matice a ij v případě neorientovaného grafu je roven počtu hran spojujících vrcholy i a j. Pro orientovaný graf je prvek a ij roven počtu hran směřujících z vrcholu i do vrcholu j.

Základní věty týkající se maticových reprezentací grafů.

1). Pořadí (maximální počet lineárně nezávislých sloupců) matice výskytu A souvislého grafu (orientovaného i neorientovaného) s n vrcholy je rovno (n-1).

2). Hodnost matice cyklu C souvislého grafu s m hranami a n vrcholy je (m-n+1).

Příklad použití matice sousednosti.

Následující mapování ukazuje, že grafy G 1 a G 2 jsou izomorfní

Matice sousedství zahrnují současnou permutaci řádků a sloupců, kterou lze provést pomocí podobnostní transformace a permutační matice.

A 2 = PA 1 P", kde

P = , nebo p ij =d p(i),j (Kroneckerův symbol)

a P" je transponovaná matice.

Najít matici P může být obtížné.

Izomorfismus G 1 a G 2 znamená, že A 1 a A 2 mají stejná vlastní čísla. Tato podmínka však není dostatečná (příklad níže).