Blandad graf - Mixed graph

En blandad graf G = ( V , E , A ) är en matematisk föremål bestående av en mängd noder (eller noder ) V , en uppsättning (icke riktad) kanter E , och en uppsättning riktade kanter (eller bågar) A .

Definitioner och notering

Tänk på intilliggande hörn . En riktad kant , kallad en båge , är en kant med en orientering och kan betecknas som eller (notera att det är svansen och är bågens huvud). En oriktad kant eller kant är också en kant utan orientering och kan betecknas som eller . ${\ displaystyle u, v \ in V}$${\ displaystyle {\ overrightarrow {uv}}}$${\ displaystyle (u, v)}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle uv}$${\ displaystyle [u, v]}$

För tillämpningsexemplet kommer vi inte att överväga slingor eller flera kanter av blandade grafer.

En promenad i en blandad graf är en sekvens av hörn och kanter/bågar så att för alla index är antingen en kant av grafen eller en båge i grafen. Denna promenad är en väg om den inte upprepar några kanter, bågar eller hörn, förutom möjligen de första och sista hörnen. En väg är stängd om dess första och sista hörn är desamma, och en stängd väg är en cykel om den inte upprepar hörn, förutom den första och den 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 i}$${\ displaystyle c_ {i} = v_ {i} v_ {i+1}}$${\ displaystyle c_ {i} = {\ overrightarrow {v_ {i} v_ {i+1}}}}}$

Färg

Blandad graffärgning kan ses som en märkning eller en tilldelning av k olika färger (där k är ett positivt heltal) till hörnen i en blandad graf. Olika färger måste tilldelas hörn som är anslutna med en kant. Färgerna kan representeras av siffrorna från 1 till k , och för en riktad båge måste svansens svans vara färgad med ett mindre tal än bågens huvud.

Exempel

Tänk till exempel på figuren till höger. Våra tillgängliga k-färger för att färga vår blandade graf är . Eftersom och är anslutna med en kant måste de få olika färger eller märkningar ( och är märkta 1 respektive 2). Vi har också en båge från till . Eftersom orientering tilldelar en 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 u}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle v}$${\ displaystyle w}$

Stark och svag färgning

En (stark) korrekt k -färgning av en blandad graf är en funktion

${\ displaystyle c: V \ högerpil [k]}$där så att om och om . ${\ displaystyle [k]: = {1,2, \ dots, k}}$${\ displaystyle c (u) \ neq c (v)}$${\ displaystyle uv \ i E}$${\ displaystyle c (u) <c (v)}$${\ displaystyle {\ overrightarrow {uv}} \ i A}$

Ett svagare tillstånd på våra bågar kan tillämpas och vi kan betrakta en svag korrekt k -färgning av en blandad graf som en funktion

${\ displaystyle c: V \ högerpil [k]}$där så att om och om . Med hänvisning till vårt exempel betyder det att vi kan märka både huvud och svans med det positiva heltalet 2. ${\ displaystyle [k]: = {1,2, \ dots, k}}$${\ displaystyle c (u) \ neq c (v)}$${\ displaystyle uv \ i E}$${\ displaystyle c (u) \ leq c (v)}$${\ displaystyle {\ overrightarrow {uv}} \ i A}$${\ displaystyle (v, w)}$

Existens

En färgning kan finnas eller inte för en blandad graf. För att en blandad graf ska ha en k-färgning kan grafen inte innehålla några riktade cykler. Om det finns en sådan k-färgning, hänvisar vi till det minsta k som behövs för att korrekt färga vår graf som det kromatiska talet , betecknat . Vi kan räkna antalet korrekta k-färgningar som en polynomfunktion av k. Detta kallas det kromatiska polynomet för vårt diagram G (i analogi med det kromatiska polynomet för oriktade grafer) och kan betecknas som . ${\ displaystyle \ chi (G)}$${\ displaystyle \ chi _ {G} (k)}$

Beräkning av svaga kromatiska polynom

Den deletion-kontraktion metod kan användas för att beräkna svaga kromatiska polynom av blandade grafer. Denna metod innefattar att ta bort (eller ta bort) en kant eller båge och dra ihop (eller sammanfoga) de återstående hörnen som infaller till den kanten (eller bågen) för att bilda en hörnpunkt. Efter att ha raderat en kant, från ett blandat diagram får vi det blandade diagrammet . Vi kan beteckna denna radering av kanten , som . På samma sätt, genom att radera en båge,, från en blandad graf, får vi var vi kan beteckna radering av som . Dessutom kan vi beteckna sammandragning av och som och , respektive. Från givna propositioner får vi följande ekvationer för att beräkna det kromatiska polynomet för en blandad graf: ${\ displaystyle e}$${\ displaystyle G = (V, E, A)}$${\ displaystyle (V, Ee, A)}$${\ displaystyle e}$${\ displaystyle Ge}$${\ displaystyle a}$${\ displaystyle (V, E, Aa)}$${\ displaystyle a}$${\ displaystyle Ga}$${\ displaystyle e}$${\ displaystyle a}$${\ displaystyle G/e}$${\ displaystyle G/a}$

1. ${\ displaystyle \ chi _ {G} (k) = \ chi _ {Ge} (k)-\ chi _ {G/e} (k)}$,
2. ${\ displaystyle \ chi _ {G} (k) = \ chi _ {Ga} (k)+\ chi _ {G/a} (k)-\ chi _ {G_ {a}} (k)}$.

Ansökningar

Schemaläggningsproblem

Blandade grafer kan användas för att modellera jobbschemaläggningsproblem där en samling uppgifter ska utföras, med förbehåll för vissa tidsbegränsningar. I denna typ av problem kan oriktade kanter användas för att modellera en begränsning av att två uppgifter är inkompatibla (de kan inte utföras samtidigt). Riktade kanter kan användas för att modellera prioritetsbegränsningar, där en uppgift måste utföras före den andra. En graf som definieras på detta sätt från ett schemaläggningsproblem kallas en disjunktiv graf . Problemet med blandad graffärgning kan användas för att hitta ett schema med minsta längd för att utföra alla uppgifter.

Bayesisk slutsats

Blandade grafer används också som grafiska modeller för Bayesiansk slutsats . I detta sammanhang kallas också en acyklisk blandad graf (en utan cykler av riktade kanter) också en kedjediagram . De riktade kanterna på dessa grafer används för att indikera ett orsakssamband mellan två händelser, där resultatet av den första händelsen påverkar sannolikheten för den andra händelsen. Oriktade kanter indikerar istället en icke-orsakssamband mellan två händelser. En ansluten komponent i den ostyrda undergrafen till ett kedjediagram kallas en kedja. Ett kedjediagram kan omvandlas till ett oriktat diagram genom att konstruera dess moraldiagram , ett oriktat diagram som bildas av kedjediagrammet genom att lägga till oriktade kanter mellan par av hörn som har utgående kanter till samma kedja och sedan glömma riktningarna för de riktade kanterna .

Anteckningar

Referenser

• Beck, M .; Blado, D .; Crawford, J .; Jean-Louis, T .; Young, M. (2013), "Om svaga kromatiska polynom av blandade grafer", Graphs and Combinatorics , arXiv : 1210.4634 , doi : 10.1007/s00373-013-1381-1.
• Cowell, Robert G .; Dawid, A. Philip ; Lauritzen, Steffen L .; Spiegelhalter, David J. (1999), Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks , Springer-Verlag New York, sid. 27, doi : 10.1007/0-387-22630-3 , ISBN 0-387-98767-3
• Hansen, Pierre; Kuplinsky, Julio; de Werra, Dominique (1997), "Mixed graph colorings", Mathematical Methods of Operations Research , 45 (1): 145–160, doi : 10.1007/BF01194253 , MR  1435900.
• Ries, B. (2007), "Färga några klasser av blandade grafer", Diskret tillämpad matematik , 155 (1): 1–6, doi : 10.1016/j.dam.2006.05.004 , MR  2281351.

externa länkar

• Weisstein, Eric W. "Blandad graf" . MathWorld .