Blandad greve

En blandad graf G = (V, E, A) är ett matematiskt objekt som består av en uppsättning hörn (eller noder) V, en uppsättning (oriktade) kanter E och en uppsättning riktade kanter (eller bågar) A. [ 1]

Definitioner och notation

Ytterligare information: Graf (matematik)

Tänk på närliggande hörn . En orienterad kant kallas en båge , en kant med en orientering, som betecknas med eller (det är värt att notera att detta är svansen, och detta är huvudet på bågen). [2] En oriktad kant , eller helt enkelt en kant , kallas en kant utan orientering och betecknas med eller . [2] $u,v\in V$ ${\displaystyle {\displaystyle {\overrightarrow {uv))))$ ${\displaystyle {\displaystyle (u,v)))$ $u$ $v$ ${\displaystyle {\displaystyle uv))$ $[u,v]$

Ytterligare information: Flera kanter

Ytterligare information: Loop (grafteori)

Som vårt applikationsexempel kommer vi inte att överväga cykler eller flera kanter av blandade grafer.

En bana i en blandad graf är en sekvensav hörn och kanter/bågar så att, för alla index,kant av grafen eller elementetär en båge av grafen. Denna bana är en bana om den inte har några upprepade kanter, bågar eller hörn, utom möjligen de första och sista hörnen. En bana är stängd om dess första och sista hörn är samma, och en stängd bana är en cykel om den inte har några upprepade hörn förutom den första och sista. En blandad graf är acyklisk om den inte innehåller en cykel. ${\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))))$

Målarbok

Ytterligare information: Graffärgning

Att färglägga en blandad graf kan ses som att märka eller tilldela olika färger (där är ett positivt heltal) till hörnen på den blandade grafen. [3] Vertices förbundna med en kant måste tilldelas olika färger. Färger kan representeras av siffror från 1 till , och för en riktad båge måste svansen på bågen indikeras med en siffra som är mindre än bågens huvud. [3] $k$ $k$ $k$

Exempel

Tänk till exempel på figuren till höger. Tillgängliga k-färger för att färga vår blandade graf: . Eftersom och är förbundna med en kant måste de ha olika färger eller siffror ( och är märkta 1 respektive 2). Vi har även en båge från till . Eftersom vi har att göra med en båge där orienteringen dikterar siffrornas ordning, måste vi märka svansen ( ) med en mindre färg (eller ett heltal från vår uppsättning) än huvudet ( ) på vår båge. ${\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))$

Stark och svag färgning

Den ( starka) egen- färgningen av en blandad graf är en funktion $k$

${\displaystyle c:V\rightarrow [k]}$ , där sådan att , om , och , om . [ett] ${\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 slappna av tillståndet på våra bågar. Då kan vi betrakta den svaga korrekta k-färgningen av den blandade grafen som en funktion

${\displaystyle c:V\rightarrow [k]}$ , där sådan att , om , och , om . [1] Om vi går tillbaka till vårt exempel betyder det att vi kan märka huvudet och svansen med det positiva 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)$

Existens

För en blandad graf kan en färgning existera eller inte. För att en blandad graf ska vara -färgbar får den inte innehålla några riktade cykler. [2] Om en sådan -färgning existerar, betecknar vi det minsta som krävs för att korrekt färga vår graf som det kromatiska numret , betecknat med . [2] Vi kan räkna antalet korrekta färger som en polynomfunktion av . Detta kallas det kromatiska polynomet i vår graf (i analogi med det kromatiska polynomet för oriktade grafer) och kan betecknas som . [ett] $k$ $k$ $k$ ${\displaystyle {\displaystyle \chi (G)))$ $k$ $k$ $G$ ${\displaystyle {\displaystyle \chi _{G}(k)))$

Beräkning av svaga kromatiska polynom

Formeln för borttagning och kontraktion kan användas för att beräkna svaga kromatiska polynom av blandade grafer. Denna metod innebär att man tar bort en kant eller båge och krymper (eller sammanfogar) de återstående hörnen på den kanten (eller bågen) för att bilda en enda vertex. [1] Efter att ha tagit bort en kant från en blandad graf får vi en blandad graf . [1] Vi kan beteckna denna kantborttagning som . På liknande sätt, genom att ta bort en båge från en blandad graf, får vi , där vi kan beteckna borttagningen som . [1] Dessutom kan vi beteckna förkortningen och som respektive . [1] Från ovanstående uttalanden [1] får vi följande ekvationer för att beräkna det kromatiska polynomet för en blandad graf: $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)))$ [ett]
${\displaystyle \chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k) }$ [ett]

Applikationer

Planeringsproblem

Blandade grafer kan användas för att modellera arbetsschemaläggningsuppgifter där uppgifter måste samlas in, med vissa tidsbegränsningar. I denna typ av uppgift kan oriktade kanter användas för att modellera begränsningen att två uppgifter är inkompatibla (de kan inte köras samtidigt). Riktade kanter kan användas för att modellera prioritetsbegränsningar, där en uppgift måste slutföras före en annan. En graf som definieras på detta sätt från ett schemaläggningsproblem kallas en disjunktiv graf. Problemet med färgning av blandade grafer kan användas för att hitta minimilängden för att slutföra alla uppgifter. [2]

Bayesiansk slutledning

Blandade grafer används också som grafiska modeller för Bayesiansk slutledning . I detta sammanhang kallas en acyklisk blandad graf (utan cykler av riktade kanter) även en kedjegraf. De riktade kanterna på dessa grafer används för att indikera ett orsakssamband mellan två händelser, där utfallet av den första händelsen påverkar sannolikheten för den andra händelsen. Oriktade kanter indikerar en icke-kausal korrelation mellan två händelser. En sammankopplad komponent i en oriktad subgraf i en kedjegraf kallas en kedja. En kedjegraf kan konverteras till en oriktad graf genom att konstruera dess moraliska graf , en oriktad graf bildad från en kedjegraf genom att lägga till oriktade kanter mellan par av hörn som har utgående kanter i samma kedja, utan hänsyn till orienteringen av de riktade kanterna. [fyra]

Anteckningar

↑ 1 2 3 4 5 6 7 8 9 10 11 Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. Om svaga kromatiska polynom av blandade grafer // Grafer och kombinatorik. — 2015-01-01. — Vol. 31 , iss. 1 . — S. 91–98 . — ISSN 1435-5914 . - doi : 10.1007/s00373-013-1381-1 .
↑ 1 2 3 4 5 B. Ries. Färgläggning av några klasser av blandade grafer (engelska) // Diskret tillämpad matematik. - 2007-01-01. — Vol. 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. Blandade graffärger (engelska) // Mathematical Methods of Operations Research. - 1997-02-01. — Vol. 45 , iss. 1 . — S. 145–160 . — ISSN 1432-5217 . - doi : 10.1007/BF01194253 .
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Probabilistiska nätverk och expertsystem: Exakta beräkningsmetoder för Bayesianska nätverk . — Springer Science & Business Media, 2007-07-16. — 340 s. - ISBN 978-0-387-71823-1 .

Länkar

Weisstein, Eric W. "Mixed Graph" MathWorld