Smíšený počet

Smíšený graf G = (V, E, A) je matematický objekt skládající se z množiny vrcholů (nebo uzlů) V, množiny (neorientovaných) hran E a množiny orientovaných hran (nebo oblouků) A. [ 1]

Definice a zápis

Další informace: Graf (matematika)

Zvažte sousední vrcholy . Orientovaná hrana se nazývá oblouk , hrana s orientací, která je označena nebo (za zmínku stojí, že toto je konec a toto je hlava oblouku). [2] Neorientovaná hrana , nebo jednoduše hrana , se nazývá hrana bez orientace a značí se nebo . [2] $u,v\in V$ ${\displaystyle {\displaystyle {\overrightarrow {uv))))$ ${\displaystyle {\displaystyle (u,v)))$ $u$ $proti$ ${\displaystyle {\displaystyle uv))$ $[u,v]$

Další informace: Více hran

Další informace: Loop (teorie grafů)

Jako příklad naší aplikace nebudeme uvažovat cykly nebo vícenásobné hrany smíšených grafů.

Cesta ve smíšeném grafu je posloupnostvrcholů a hran/oblouků tak, že pro všechny indexyjehrana grafu, nebo je prvekoblouk grafu. Tato cesta je cestou , pokud nemá žádné opakované hrany, oblouky nebo vrcholy, s výjimkou prvního a posledního vrcholu. Cesta je uzavřená , pokud jsou její první a poslední vrcholy stejné, a uzavřená cesta je cyklus , pokud nemá žádné jiné opakující se vrcholy než první a poslední. Smíšený graf je acyklický , pokud neobsahuje cyklus. ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k))$ ${\displaystyle {\displaystyle i))$ ${\displaystyle c_{i}=v_{i}v_{i+1))$ ${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1))))$

Omalovánka

Další informace: Barvení grafu

Obarvení smíšeného grafu lze považovat za označení nebo přiřazení různých barev (kde je kladné celé číslo) vrcholům smíšeného grafu. [3] Vrcholy spojené hranou musí mít přiřazeny různé barvy. Barvy mohou být reprezentovány čísly od 1 do , a pro směrovaný oblouk musí být konec oblouku označen číslem menším, než je hlava oblouku. [3] $k$ $k$ $k$

Příklad

Vezměme si například obrázek vpravo. Dostupné k-barvy pro vybarvení našeho smíšeného grafu: . Protože a jsou spojeny hranou, musí mít různé barvy nebo čísla ( a jsou označeny 1 a 2). Máme také oblouk od do . Protože máme co do činění s obloukem, kde orientace určuje pořadí čísel, musíme označit konec ( ) menší barvou (nebo celým číslem z naší sady) než je hlava ( ) našeho oblouku. ${\displaystyle \{1,2,3\))$ ${\displaystyle {\displaystyle u))$ ${\displaystyle {\displaystyle v))$ ${\displaystyle {\displaystyle u))$ ${\displaystyle {\displaystyle v))$ ${\displaystyle {\displaystyle v))$ ${\displaystyle {\displaystyle w))$ ${\displaystyle {\displaystyle v))$ ${\displaystyle {\displaystyle w))$

Silné a slabé zbarvení

( silné) vlastní zbarvení smíšeného grafu je funkce $k$

${\displaystyle c:V\rightarrow [k]}$ , kde takové, že , jestliže , a , jestliže . [jeden] ${\displaystyle [k]:={1,2,\tečky ,k))$ ${\displaystyle {\displaystyle c(u)\neq c(v)))$ ${\displaystyle {\displaystyle uv\in E))$ ${\displaystyle {\displaystyle c(u)<c(v)))$ ${\displaystyle {\overrightarrow {uv}}\in A}$

Můžeme uvolnit stav na našich obloucích. Pak můžeme považovat slabé správné k-zabarvení smíšeného grafu za funkci

${\displaystyle c:V\rightarrow [k]}$ , kde takové, že , jestliže , a , jestliže . [1] Vrátíme- li se k našemu příkladu, znamená to, že hlavu a ocas můžeme označit kladným celým číslem 2. ${\displaystyle [k]:={1,2,\tečky ,k))$ ${\displaystyle {\displaystyle c(u)\neq c(v)))$ ${\displaystyle {\displaystyle uv\in E))$ ${\displaystyle {\displaystyle c(u)\leq c(v)))$ ${\displaystyle {\overrightarrow {uv}}\in A}$ $(v,w)$

Existence

U smíšeného grafu může nebo nemusí existovat zbarvení. Aby byl smíšený graf -barvitelný, nesmí obsahovat žádné směrované cykly. [2] Pokud takové -zabarvení existuje, pak nejmenší potřebné pro správné obarvení našeho grafu označíme jako chromatické číslo , označené . [2] Můžeme počítat počet správných zabarvení jako polynomiální funkci . Toto se nazývá chromatický polynom našeho grafu (analogicky s chromatickým polynomem neorientovaných grafů) a lze jej označit jako . [jeden] $k$ $k$ $k$ ${\displaystyle {\displaystyle \chi (G)))$ $k$ $k$ $G$ ${\displaystyle {\displaystyle \chi _{G}(k)))$

Výpočet slabě chromatických polynomů

Vzorec delece-kontrakce lze použít k výpočtu slabě chromatických polynomů smíšených grafů. Tato metoda zahrnuje odstranění hrany nebo oblouku a zmenšení (nebo spojení) zbývajících vrcholů na této hraně (nebo oblouku) do jediného vrcholu. [1] Po odstranění hrany ze smíšeného grafu dostaneme smíšený graf . [1] Toto odstranění hrany můžeme označit jako . Podobně odstraněním oblouku ze smíšeného grafu dostaneme , kde odstranění můžeme označit jako . [1] Kromě toho můžeme označovat zkratku a jako a , resp. [1] Z výše uvedených tvrzení [1] získáme následující rovnice pro výpočet chromatického polynomu smíšeného grafu: $E$ $G=(V,E,A)$ $(V,Ee,A)$ $E$ $Ge$ $A$ $(V,E,Aa)$ $A$ $Ga$ $E$ $A$ $G/e$ $G/a$

${\displaystyle {\displaystyle \mathrm {X} _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k)))$ [jeden]
${\displaystyle \chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k) }$ [jeden]

Aplikace

Problém plánování

Smíšené grafy lze použít k modelování úkolů plánování práce, ve kterých musí být úkoly shromažďovány, s výhradou určitých časových omezení. V tomto typu úloh lze neorientované hrany použít k modelování omezení, že dvě úlohy nejsou kompatibilní (nelze je provést současně). Nasměrované hrany lze použít k modelování prioritních omezení, ve kterých musí být jeden úkol dokončen před druhým. Takto definovaný graf z rozvrhovacího problému se nazývá disjunktivní graf. Problém smíšeného zbarvení grafu lze použít k nalezení plánu minimální délky pro dokončení všech úkolů. [2]

Bayesovský závěr

Smíšené grafy se také používají jako grafické modely pro Bayesovskou inferenci . V této souvislosti se acyklický smíšený graf (bez cyklů směrovaných hran) nazývá také řetězový graf. Orientované hrany těchto grafů se používají k označení kauzálního vztahu mezi dvěma událostmi, ve kterých výsledek první události ovlivňuje pravděpodobnost druhé události. Neorientované hrany indikují nekauzální korelaci mezi dvěma událostmi. Souvislá složka neorientovaného podgrafu řetězového grafu se nazývá řetězec. Řetězový graf lze převést na neorientovaný graf vytvořením jeho morálního grafu , neorientovaný graf vytvořený z řetězového grafu přidáním neorientovaných hran mezi páry vrcholů, které mají odchozí hrany ve stejném řetězci, bez ohledu na orientaci nasměrovaných hran. [čtyři]

Poznámky

↑ 1 2 3 4 5 6 7 8 9 10 11 Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. O slabých chromatických polynomech smíšených grafů // Grafy a kombinatorika. — 2015-01-01. — Sv. 31 , iss. 1 . — S. 91–98 . — ISSN 1435-5914 . - doi : 10.1007/s00373-013-1381-1 .
↑ 1 2 3 4 5 B. Ries. Vybarvování některých tříd smíšených grafů (anglicky) // Discrete Applied Mathematics. - 2007-01-01. — Sv. 155 , iss. 1 . — S. 1–6 . — ISSN 0166-218X . - doi : 10.1016/j.dam.2006.05.004 .
↑ 1 2 Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Obarvení smíšených grafů (anglicky) // Matematické metody operačního výzkumu. - 1997-02-01. — Sv. 45 , iss. 1 . — S. 145–160 . — ISSN 1432-5217 . - doi : 10.1007/BF01194253 .
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Pravděpodobnostní sítě a expertní systémy: Exaktní výpočetní metody pro Bayesovské sítě . — Springer Science & Business Media, 2007-07-16. — 340 s. - ISBN 978-0-387-71823-1 .

Odkazy

Weisstein, Eric W. "Smíšený graf" MathWorld