Blandet Greve

En blandet graf G = (V, E, A) er et matematisk objekt bestående af et sæt toppunkter (eller noder) V, et sæt (urettede) kanter E og et sæt rettede kanter (eller buer) A. [ 1]

Definitioner og notation

Yderligere information: Graf (matematik)

Overvej tilstødende hjørner . En orienteret kant kaldes en bue , en kant med en orientering, som er betegnet med eller (det er værd at bemærke, at dette er halen, og dette er hovedet af buen). [2] En urettet kant , eller blot en kant , kaldes en kant uden orientering og betegnes med eller . [2] $u,v\in V$ ${\displaystyle {\displaystyle {\overrightarrow {uv))))$ ${\displaystyle {\displaystyle (u,v)))$ $u$ $v$ ${\displaystyle {\displaystyle uv))$ $[u,v]$

Yderligere information: Flere kanter

Yderligere information: Loop (grafteori)

Som vores applikationseksempel vil vi ikke overveje cyklusser eller flere kanter af blandede grafer.

En sti i en blandet graf er en sekvensaf hjørner og kanter/buer, således at for alle indekserentenkant af grafen, eller elementeter en bue af grafen. Denne sti er en sti, hvis den ikke har gentagne kanter, buer eller spidser, undtagen muligvis de første og sidste spidser. En sti er lukket , hvis dens første og sidste knudepunkter er ens, og en lukket sti er en cyklus, hvis den ikke har andre gentagne knudepunkter end den første og sidste. En blandet graf er acyklisk , hvis den ikke indeholder en 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))))$

Farvelægningsside

Yderligere information: Graffarvning

Farvelægning af en blandet graf kan opfattes som at mærke eller tildele forskellige farver (hvor er et positivt heltal) til hjørnerne af den blandede graf. [3] Hjørner forbundet med en kant skal tildeles forskellige farver. Farver kan repræsenteres med tal fra 1 til , og for en rettet bue skal buens hale angives med et tal mindre end buens hoved. [3] $k$ $k$ $k$

Eksempel

Overvej for eksempel figuren til højre. Tilgængelige k-farver til farvning af vores blandede graf: . Da og er forbundet med en kant, skal de have forskellige farver eller tal ( og er mærket henholdsvis 1 og 2). Vi har også en bue fra til . Da vi har at gøre med en bue, hvor orienteringen dikterer rækkefølgen af tal, skal vi mærke halen ( ) med en mindre farve (eller et heltal fra vores sæt) end hovedet ( ) af vores bue. ${\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))$

Stærk og svag farve

Den ( stærke) egen - farvning af en blandet graf er en funktion $k$

${\displaystyle c:V\rightarrow [k]}$ , hvor sådan at , hvis , og , hvis . [en] ${\displaystyle [k]:={1,2,\dots ,k))$ ${\displaystyle {\displaystyle c(u)\neq c(v)))$ ${\displaystyle {\displaystyle uv\in E))$ ${\displaystyle {\displaystyle c(u)<c(v)))$ ${\displaystyle {\overrightarrow {uv}}\in A}$

Vi kan slappe af tilstanden på vores buer. Så kan vi betragte den svage korrekte k-farvning af den blandede graf som en funktion

${\displaystyle c:V\rightarrow [k]}$ , hvor sådan at , hvis , og , hvis . [1] Går vi tilbage til vores eksempel, betyder det, at vi kan mærke hovedet og halen med det positive heltal 2. ${\displaystyle [k]:={1,2,\dots ,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)$

Eksistens

For en blandet graf eksisterer der muligvis en farvelægning. For at en blandet graf kan farves, må den ikke indeholde nogen rettede cyklusser. [2] Hvis en sådan -farvning eksisterer, så betegner vi den mindste , der kræves for korrekt at farve vores graf, som det kromatiske tal , angivet med . [2] Vi kan tælle antallet af egen-farvninger som en polynomisk funktion af . Dette kaldes det kromatiske polynomium i vores graf (i analogi med det kromatiske polynomium af urettede grafer) og kan betegnes som . [en] $k$ $k$ $k$ ${\displaystyle {\displaystyle \chi (G)))$ $k$ $k$ $G$ ${\displaystyle {\displaystyle \chi _{G}(k)))$

Beregning af svage kromatiske polynomier

Sletnings-kontraktionsformlen kan bruges til at beregne svage kromatiske polynomier af blandede grafer. Denne metode involverer at fjerne en kant eller bue og krympe (eller samle) de resterende hjørner på den kant (eller bue) for at danne et enkelt toppunkt. [1] Efter at have fjernet en kant fra en blandet graf, får vi en blandet graf . [1] Vi kan betegne denne kantfjernelse som . På samme måde får vi ved at fjerne en bue fra en blandet graf , hvor vi kan betegne fjernelsen som . [1] Derudover kan vi betegne henholdsvis forkortelsen og som og . [1] Fra ovenstående udsagn [1] får vi følgende ligninger til beregning af det kromatiske polynomium af en blandet graf: $e$ $G=(V,E,A)$ $(V,Ee,A)$ $e$ $Ge$ $-en$ $(V,E,Aa)$ $-en$ $Ga$ $e$ $-en$ $G/e$ $G/a$

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

Ansøgninger

Planlægningsproblem

Blandede grafer kan bruges til at modellere arbejdsplanlægningsopgaver, hvor opgaver skal indsamles, underlagt visse tidsbegrænsninger. I denne type opgave kan urettede kanter bruges til at modellere begrænsningen om, at to opgaver er inkompatible (de kan ikke udføres på samme tid). Styrede kanter kan bruges til at modellere prioritetsbegrænsninger, hvor en opgave skal udføres før en anden. En graf defineret på denne måde fra et planlægningsproblem kaldes en disjunktiv graf. Problemet med blandet graffarvning kan bruges til at finde minimumslængdeplanen for at fuldføre alle opgaver. [2]

Bayesiansk inferens

Blandede grafer bruges også som grafiske modeller for Bayesiansk inferens . I denne sammenhæng kaldes en acyklisk blandet graf (uden cyklusser af rettede kanter) også en kædegraf. De rettede kanter af disse grafer bruges til at angive en årsagssammenhæng mellem to hændelser, hvor udfaldet af den første hændelse påvirker sandsynligheden for den anden hændelse. Urettede kanter indikerer en ikke-kausal sammenhæng mellem to hændelser. En forbundet komponent af en urettet undergraf i en kædegraf kaldes en kæde. En kædegraf kan konverteres til en urettet graf ved at konstruere dens moralske graf , en urettet graf dannet ud fra en kædegraf ved at tilføje urettede kanter mellem par af hjørner, der har udgående kanter i samme kæde, uden at tage hensyn til orienteringen af de rettede kanter. [fire]

Noter

↑ 1 2 3 4 5 6 7 8 9 10 11 Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. Om svage kromatiske polynomier af blandede grafer // Grafer og kombinatorik. — 2015-01-01. — Bd. 31 , udg. 1 . — S. 91–98 . — ISSN 1435-5914 . - doi : 10.1007/s00373-013-1381-1 .
↑ 1 2 3 4 5 B. Ries. Farvelægning af nogle klasser af blandede grafer (engelsk) // Diskret anvendt matematik. - 2007-01-01. — Bd. 155 , udg. 1 . — S. 1–6 . — ISSN 0166-218X . - doi : 10.1016/j.dam.2006.05.004 .
↑ 1 2 Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Blandede graffarver (engelsk) // Mathematical Methods of Operations Research. - 1997-02-01. — Bd. 45 , iss. 1 . — S. 145–160 . — ISSN 1432-5217 . - doi : 10.1007/BF01194253 .
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Probabilistiske netværk og ekspertsystemer: nøjagtige beregningsmetoder for Bayesianske netværk . — Springer Science & Business Media, 2007-07-16. - 340 sek. - ISBN 978-0-387-71823-1 .