O grafu se říká, že je rovinný, pokud jej lze nakreslit v rovině tak, že se žádná hrana nekříží.

Příklad: Graf zobrazený na obr je rovinný graf.

pandy vytvářející datový rámec

Oblast grafu: Uvažujme rovinný graf G=(V,E). Oblast je definována jako oblast roviny, která je ohraničena hranami a nelze ji dále dělit. Rovinný graf rozděluje plány do jedné nebo více oblastí. Jedna z těchto oblastí bude nekonečná.

Konečná oblast: Pokud je oblast oblasti konečná, pak se tato oblast nazývá konečná oblast.

Nekonečná oblast: Pokud je oblast oblasti nekonečná, nazývá se tato oblast nekonečnou oblastí. Rovinný graf má pouze jednu nekonečnou oblast.

Příklad: Uvažujme graf zobrazený na obr Určete počet oblastí, konečných oblastí a nekonečnou oblast.

Řešení: Ve výše uvedeném grafu je pět regionů, tj₁,r₂,r₃,r₄,r₅.

V grafu jsou čtyři konečné oblasti, tj. r₂,r₃,r₄,r₅.

Existuje pouze jedna konečná oblast, tj. r₁

Vlastnosti rovinných grafů:

1. Pokud má souvislý rovinný graf G e hran a r oblastí, pak r ≦ To je.
2. Pokud má souvislý rovinný graf G e hran, v vrcholů a r oblastí, pak v-e+r=2.
3. Pokud má souvislý rovinný graf G e hran a v vrcholů, pak 3v-e≧6.
4. Kompletní graf K_nje rovinný právě tehdy, když n<5.< li>
5. Kompletní bipartitní graf K_mnje rovinný právě tehdy, když m3.

Příklad: Dokažte, že celý graf K₄je rovinný.

Řešení: Kompletní graf K₄obsahuje 4 vrcholy a 6 hran.

Víme, že pro souvislý rovinný graf 3v-e≧6. Pro K₄, máme 3x4-6=6, což splňuje vlastnost (3).

parseint java

Tak K₄je rovinný graf. Proto Proved.

Nerovinný graf:

O grafu se říká, že je nerovinný, pokud jej nelze nakreslit v rovině tak, aby se žádná hrana neprotínala.

Příklad: Grafy zobrazené na obr jsou nerovinné grafy.

Tyto grafy nelze kreslit v rovině, aby se žádné hrany nekřížily, jedná se tedy o nerovinné grafy.

Vlastnosti nerovinných grafů:

Graf je nerovinný právě tehdy, když obsahuje podgraf homeomorfní ke K₅nebo K_3.3

plná sčítačka

Příklad1: Ukažte, že K₅je nerovinná.

Řešení: Kompletní graf K₅obsahuje 5 vrcholů a 10 hran.

Nyní pro souvislý rovinný graf 3v-e≧6.

Proto pro K₅, máme 3 x 5-10=5 (což nesplňuje vlastnost 3, protože musí být větší nebo rovna 6).

Tedy K₅je nerovinný graf.

Příklad2: Ukažte, že grafy zobrazené na obr jsou nerovinné tím, že naleznete podgraf homeomorfní ke K₅nebo K_3.3.

Řešení: Pokud odstraníme okraje (V₁,V₄),(V₃,V₄) a (V₅,V₄) graf G₁, stane se homeomorfním na K₅.Proto je nerovinný.

Pokud odstraníme okraj V_2,V7) graf G₂se stává homeomorfní pro K_3.3.Proto je nerovinný.

Barvení grafu:

Předpokládejme, že G= (V,E) je graf bez více hran. Barvení vrcholu G je přiřazení barev k vrcholům G tak, že sousední vrcholy mají různé barvy. Graf G je M-Colorable, pokud existuje zbarvení G, které používá M-Colors.

Správné zbarvení: Zbarvení je správné, pokud jakékoli dva sousední vrcholy uav mají různé barvy, jinak se nazývá nesprávné zbarvení.

rozdíl mezi binárním stromem a binárním vyhledávacím stromem

Příklad: Zvažte následující graf a barvu C={r, w, b, y}. Vybarvěte graf správně pomocí všech barev nebo méně barev.

Graf zobrazený na obr. je minimálně 3-barevný, proto x(G)=3

Řešení: Obrázek ukazuje graf správně vybarvený všemi čtyřmi barvami.

Obr ukazuje graf správně vybarvený třemi barvami.

Chromatické číslo G: Minimální počet barev potřebný k vytvoření správného vybarvení grafu G se nazývá chromatické číslo G a označuje se x(G).

Příklad: chromatické číslo K_nje n.

Řešení: Zbarvení K_nlze konstruovat pomocí n barev přiřazením různých barev každému vrcholu. Žádné dva vrcholy nemohou mít stejné barvy, protože každé dva vrcholy tohoto grafu sousedí. Odtud chromatické číslo K_n=n.

Aplikace barvení grafů

Některé aplikace barvení grafů zahrnují:

• Registrovat přidělení
• Zbarvení mapy
• Kontrola bipartitního grafu
• Přidělování mobilních rádiových frekvencí
• Sestavení jízdního řádu atd.

Uveďte a dokažte větu o podání ruky.

Věta o podání ruky: Součet stupňů všech vrcholů v grafu G je roven dvojnásobku počtu hran v grafu.

Matematicky to lze říci takto:

∑_v∈Vstupeň(v)=2e

Důkaz: Nechť G = (V, E) je graf, kde V = {v₁,v₂, . . . . . . . . . .} je množina vrcholů a E = {e₁,To je₂. . . . . . . . . .} být množina hran. Víme, že každá hrana leží mezi dvěma vrcholy, takže každému vrcholu poskytuje stupeň jedna. Každá hrana tedy přispívá ke druhému stupni grafu. Součet stupňů všech vrcholů je tedy roven dvojnásobku počtu hran v G.

Proto, ∑_v∈Vstupeň(v)=2e

c programy