Multigraph - Multigraph

En multigraf med flera kanter (röd) och flera slingor (blå). Inte alla författare tillåter att multigrafer har slingor.

I matematik , och mer specifikt i grafteori , är en multigraf (i motsats till en enkel graf) en graf som är tillåten att ha flera kanter (även kallad parallella kanter ), det vill säga kanter som har samma slutnoder . Således kan två toppar kopplas samman med mer än en kant.

Det finns två distinkta uppfattningar om flera kanter:

• Kanter utan egen identitet : En kants identitet definieras enbart av de två noderna som den ansluter. I detta fall betyder termen "flera kanter" att samma kant kan uppstå flera gånger mellan dessa två noder.
• Kanter med egen identitet : Kanter är primitiva enheter precis som noder. När flera kanter ansluter två noder är det olika kanter.

En multigraph skiljer sig från en hypergraf , som är ett diagram där en kant kan ansluta valfritt antal noder, inte bara två.

För vissa författare är termerna pseudograf och multigraf . För andra är en pseudograf en multigraf som är tillåten att ha slingor .

Odirigerad multigraf (kanter utan egen identitet)

En multigraf G är ett ordnat par G : = ( V , E ) med

• V en uppsättning av hörn eller noder ,
• E en multiset av oordnade par av vertikaler, kallade kanter eller linjer .

Odirigerad multigraf (kanter med egen identitet)

En multigraf G är en beställd trippel G : = ( V , E , r ) med

• V en uppsättning av hörn eller noder ,
• E en uppsättning av kanter eller linjer ,
• r  : E → {{ x , y }: x , y ∈ V }, tilldelar varje kant ett oordnat par av slutpunktsnoder.

Vissa författare tillåter multigrafer att ha slingor , det vill säga en kant som kopplar en toppunkt till sig själv, medan andra kallar dessa pseudografier och reserverar termen multigraf för fallet utan slingor.

Riktad multigraf (kanter utan egen identitet)

En multidigraph är ett riktat diagram som är tillåtet att ha flera bågar, dvs bågar med samma källa och målnoder. En multidigraph G är ett ordnat par G : = ( V , A ) med

• V en uppsättning av hörn eller noder ,
• En multiset av ordnade par av vertikaler som kallas riktade kanter , bågar eller pilar .

En blandad multigraf G : = ( V , E , A ) kan definieras på samma sätt som en blandad graf .

Riktad multigraf (kanter med egen identitet)

En multidigraph eller kväver G är en beställd 4-tuple G : = ( V , A , s , t ) med

• V en uppsättning av hörn eller noder ,
• En en uppsättning av kanter eller linjer ,
• ${\ displaystyle s: A \ rightarrow V}$, tilldelar varje källa sin källnod,
• ${\ displaystyle t: A \ högerrow V}$, tilldelar varje kant sin målnod.

Denna uppfattning kan användas för att modellera de möjliga flygförbindelser som ett flygbolag erbjuder. I detta fall skulle multigrafen vara en riktad graf med par riktade parallella kanter som förbinder städer för att visa att det är möjligt att flyga både till och från dessa platser.

I kategoriteori kan en liten kategori definieras som en multidigraph (med kanter som har sin egen identitet) utrustad med en associativ kompositionlag och en utmärkt självslinga vid varje toppunkt som fungerar som vänster och höger identitet för komposition. Av denna anledning betecknas i kategoriteori vanligtvis grafen "multidigraph", och den underliggande multidigrafen i en kategori kallas dess underliggande digraph .

märkning

Multigrafer och multidigrafer stödjer också begreppet grafmärkning , på liknande sätt. Det finns dock ingen enhet i terminologin i detta fall.

Definitionerna av märkta multigrafer och märkta multidigrafer är liknande, och vi definierar endast de senare här.

Definition 1 : En märkt multidigraph är en märkt graf med märkta bågar.

Formellt: En märkt multidigraph G är en multigraf med märkta toppar och bågar. Formellt är det en 8-tuple var ${\ displaystyle G = (\ Sigma _ {V}, \ Sigma _ {A}, V, A, s, t, \ ell _ {V}, \ ell _ {A})}$

• V är en uppsättning av vertikaler och A är en uppsättning bågar.
• ${\ displaystyle \ Sigma _ {V}}$och är ändliga alfabet för tillgängliga vertex- och bågetiketter,${\ displaystyle \ Sigma _ {A}}$
• ${\ displaystyle s \ colon A \ rightarrow \ V}$och är två kartor, som visar källan och målet vertex av en båge,${\ displaystyle t \ colon A \ rightarrow \ V}$
• ${\ displaystyle \ ell _ {V} \ colon V \ rightarrow \ Sigma _ {V}}$och är två kartor som beskriver märkningen av topparna och bågarna.${\ displaystyle \ ell _ {A} \ colon A \ rightarrow \ Sigma _ {A}}$

Definition 2 : En märkt multidigraph är en märkt graf med flera märkta bågar, dvs bågar med samma ändhörn och samma bågetikett (notera att denna uppfattning om en märkt graf skiljer sig från uppfattningen som anges i artikelgrafikmärkning ).

Se även

• Multidimensionellt nätverk
• Ordlista över grafteoriska termer
• Grafteori

anteckningar

referenser

• Balakrishnan, VK (1997). Grafteori . McGraw-Hill. ISBN  0-07-005489-4 .
• Bollobás, Béla (2002). Modern grafteori . Examenstexter i matematik . 184 . Springer. ISBN  0-387-98488-7 .
• Chartrand, Gary ; Zhang, Ping (2012). En första kurs i grafteori . Dover. ISBN  978-0-486-48368-9 .
• Diestel, Reinhard (2010). Grafteori . Examenstexter i matematik. 173 (4: e upplagan). Springer. ISBN  978-3-642-14278-9 .
• Gross, Jonathan L .; Yellen, Jay (1998). Grafteori och dess tillämpningar . CRC Press. ISBN  0-8493-3982-0 .
• Gross, Jonathan L .; Yellen, Jay, eds. (2003). Handbook of Graph Theory . CRC. ISBN  1-58488-090-2 .
• Harary, Frank (1995). Grafteori . Addison Wesley. ISBN  0-201-41033-8 .
• Janson, Svante ; Knuth, Donald E .; Luczak, Tomasz; Pittel, Boris (1993). "Den jättekomponentens födelse". Slumpmässiga strukturer och algoritmer . 4 (3): 231–358. doi : 10.1002 / rsa.3240040303 . ISSN  1042-9832 . MR  1220220 .
• Wilson, Robert A. (2002). Grafer, färgläggningar och fyrafärgssatsen . Oxford Science Publ. ISBN  0-19-851062-4 .
• Zwillinger, Daniel (2002). CRC-matematiska standardtabeller och formler (31: e upplagan). Chapman & Hall / CRC. ISBN  1-58488-291-3 .

externa länkar

•  Den här artikeln innehåller material  från public domain från  NIST- dokumentet:  Black, Paul E. "Multigraph" . Ordbok för algoritmer och datastrukturer .