Vegyes gróf

A G = (V, E, A) vegyes gráf egy matematikai objektum, amely V csúcsokból (vagy csomópontokból), E (iránytalan) élek halmazából és A irányított élek (vagy ívek) halmazából áll. [ 1]

Definíciók és jelölések

További információ: Grafikon (matematika)

Tekintsük a szomszédos csúcsokat . Az orientált élt ívnek nevezzük , egy tájolású élt, amelyet vagy jelöl (érdemes megjegyezni, hogy ez a farok, ez pedig az ív feje). [2] Az irányítatlan élt vagy egyszerűen egy élt orientáció nélküli élnek nevezzük, és vagy -vel jelöljük . [2] $u,v\in V$ ${\displaystyle {\displaystyle {\overrightarrow {uv))))$ ${\displaystyle {\displaystyle (u,v)))$ $u$ $v$ ${\displaystyle {\displaystyle uv))$ $[u,v]$

További információ: Több él

További információ: Loop (gráfelmélet)

Alkalmazási példánkként nem vesszük figyelembe a kevert gráfok ciklusait vagy több élét.

A vegyes gráfban lévő útvonal csúcsok és élek/ívek sorozata, így minden indexeseténa gráf éle, vagy az elema gráf íve. Ez az útvonal egy útvonal , ha nincsenek ismétlődő élei, ívei vagy csúcsai, kivéve esetleg az első és az utolsó csúcsot. Egy útvonal akkor zárt , ha az első és az utolsó csúcsa megegyezik, a zárt út pedig ciklus , ha az első és az utolsó csúcson kívül nincs más ismétlődő csúcsa. A vegyes gráf aciklikus , ha nem tartalmaz ciklust. ${\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))))$

Színező oldal

További információ: Grafikonszínezés

A vegyes gráf színezése felfogható úgy, mint a vegyes gráf csúcsaihoz különböző színek (ahol pozitív egész szám) címkézése vagy hozzárendelése. [3] Az éllel összekötött csúcsokhoz különböző színeket kell hozzárendelni. A színek 1-től -ig számokkal ábrázolhatók, irányított ív esetén pedig az ív végét az ív fejénél kisebb számmal kell jelölni. [3] $k$ $k$ $k$

Példa

Vegyük például a jobb oldali ábrát. Vegyes grafikonunk színezéséhez elérhető k-színek: . Mivel a és egy éllel vannak összekötve, különböző színekkel vagy számokkal kell rendelkezniük ( és 1-es, illetve 2-es jelöléssel). Van egy ívünk is től ig . Mivel olyan ívről van szó, ahol a tájolás határozza meg a számok sorrendjét, a farkát ( ) kisebb színnel (vagy egész számmal a halmazunkból) kell felcímkéznünk, mint az ívünk fejét ( ). ${\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))$

Erős és gyenge színezés

A vegyes gráf ( erős) sajátszíne egy függvény $k$

${\displaystyle c:V\rightarrow [k]}$ , ahol olyan, hogy , ha , és , ha . [egy] ${\megjelenítési stílus [k]:={1,2,\pontok ,k))$ ${\displaystyle {\displaystyle c(u)\neq c(v)))$ ${\displaystyle {\displaystyle uv\in E))$ ${\displaystyle {\displaystyle c(u)<c(v)))$ ${\displaystyle {\overrightarrow {uv}}\in A}$

Lazíthatjuk az állapotot az íveinken. Ekkor a vegyes gráf gyenge megfelelő k-színezését tekinthetjük függvénynek

${\displaystyle c:V\rightarrow [k]}$ , ahol olyan, hogy , ha , és , ha . [1] Visszatérve a példánkra, ez azt jelenti, hogy a fejet és a farkát pozitív egész számmal 2 jelölhetjük. ${\megjelenítési stílus [k]:={1,2,\pontok ,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)$

Létezés

Vegyes gráf esetén előfordulhat színezés, vagy nem. Ahhoz, hogy egy vegyes gráf színezhető legyen, nem tartalmazhat irányított ciklusokat. [2] Ha létezik ilyen színezés, akkor a gráfunk megfelelő színezéséhez szükséges legkisebb számot jelöljük kromatikus számként , amelyet -vel jelölünk . [2] Megszámolhatjuk a megfelelő színezések számát a polinom függvényeként . Ezt nevezzük gráfunk kromatikus polinomjának ( a nem irányított gráfok kromatikus polinomjának analógiájára), és így jelölhetjük . [egy] $k$ $k$ $k$ ${\displaystyle {\displaystyle \chi (G)))$ $k$ $k$ $G$ ${\displaystyle {\displaystyle \chi _{G}(k)))$

Gyenge kromatikus polinomok számítása

A törlés-összehúzódás képlet használható vegyes gráfok gyenge kromatikus polinomjainak kiszámítására. Ez a módszer magában foglalja egy él vagy ív eltávolítását, és az adott élen (vagy íven) a fennmaradó csúcsok összezsugorítását (vagy összekapcsolását), hogy egyetlen csúcsot alkossanak. [1] Miután eltávolítottunk egy élt egy vegyes gráfból, egy kevert gráfot kapunk . [1] Ezt az éleltávolítást jelölhetjük . Hasonlóképpen, ha egy vegyes gráfból eltávolítunk egy ívet , azt kapjuk, ahol az eltávolítást jelölhetjük . [1] Ezen kívül jelölhetjük a rövidítést és as és , ill. [1] A fenti állításokból [1] a következő egyenleteket kapjuk egy vegyes gráf kromatikus polinomjának kiszámításához: $e$ $G=(V,E,A)$ ${\megjelenítési stílus (V,Ee,A)}$ $e$ $Ge$ $a$ ${\megjelenítési stílus (V,E,Aa)}$ $a$ $Ga$ $e$ $a$ $G/e$ $G/a$

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

Alkalmazások

Tervezési probléma

Vegyes grafikonok használhatók olyan munkaütemezési feladatok modellezésére, amelyekben a feladatokat össze kell gyűjteni, bizonyos időkorlátok függvényében. Az ilyen típusú feladatoknál az irányítatlan élek segítségével modellezhető az a kényszer, hogy két feladat nem kompatibilis (egyszerre nem hajthatók végre). Irányított élek használhatók prioritási kényszerek modellezésére, amelyekben az egyik feladatot a másik előtt kell befejezni. Az ütemezési feladatból így definiált gráfot diszjunktív gráfnak nevezzük. A vegyes grafikon színezési problémája felhasználható az összes feladat elvégzéséhez szükséges minimális hosszúságú ütemezés megkeresésére. [2]

Bayesi következtetés

A vegyes gráfokat grafikus modellként is használják a Bayes-i következtetésekhez . Ebben az összefüggésben az aciklikus vegyes gráfot (irányított élciklusok nélkül) láncgráfnak is nevezik. Ezen grafikonok irányított élei két esemény közötti ok-okozati összefüggést jeleznek, amelyben az első esemény kimenetele befolyásolja a második esemény valószínűségét. Az irányítatlan élek nem oksági összefüggést jeleznek két esemény között. Egy láncgráf irányítatlan részgráfjának összefüggő összetevőjét láncnak nevezzük. Egy láncgráf átalakítható irányítatlan gráfrá, ha megszerkeszti a morális gráfját , egy irányítatlan gráfot, amelyet láncgráfból úgy alakítunk ki, hogy irányítatlan éleket adunk olyan csúcspárok közé, amelyeknek ugyanabban a láncban vannak kimenő élei, figyelmen kívül hagyva az irányított élek orientációját. [négy]

Jegyzetek

↑ 1 2 3 4 5 6 7 8 9 10 11 Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. A vegyes gráfok gyenge kromatikus polinomjairól // Gráfok és kombinatorika. — 2015-01-01. — Vol. 31 , iss. 1 . — P. 91–98 . — ISSN 1435-5914 . - doi : 10.1007/s00373-013-1381-1 .
↑ 1 2 3 4 5 B. Ries. A vegyes gráfok egyes osztályainak kiszínezése (angol) // Discrete Applied Mathematics. - 2007-01-01. — Vol. 155 , iss. 1 . — P. 1–6 . — ISSN 0166-218X . - doi : 10.1016/j.dam.2006.05.004 .
↑ 1 2 Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Vegyes gráfszínezések (angol) // A műveletek kutatásának matematikai módszerei. - 1997-02-01. — Vol. 45 , iss. 1 . — P. 145–160 . — ISSN 1432-5217 . - doi : 10.1007/BF01194253 .
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Valószínűségi hálózatok és szakértői rendszerek: pontos számítási módszerek Bayes-hálózatokhoz . — Springer Science & Business Media, 2007.07.16. — 340 s. - ISBN 978-0-387-71823-1 .

Linkek

Weisstein, Eric W. "Mixed Graph" MathWorld