Multigraf - Multigraph

Multigraf s více hranami (červený) a několika smyčkami (modrý). Ne všichni autoři umožňují multigrafům mít smyčky.

V matematice a konkrétněji v teorii grafů je multigraf (na rozdíl od jednoduchého grafu) graf, u kterého je povoleno mít více hran (nazývaných také paralelní hrany ), tj. Hrany, které mají stejné koncové uzly . Dva vrcholy tedy mohou být spojeny více než jednou hranou.

Existují dva odlišné pojmy více hran:

• Hrany bez vlastní identity : Identita hrany je definována pouze dvěma uzly, které spojuje. V tomto případě termín „více hran“ znamená, že mezi těmito dvěma uzly může několikrát dojít ke stejné hraně.
• Hrany s vlastní identitou : Hrany jsou primitivní entity stejně jako uzly. Když více hran spojuje dva uzly, jedná se o různé hrany.

Multigraf se liší od hypergrafu , což je graf, ve kterém hrana může spojit libovolný počet uzlů, nejen dva.

Pro některé autory jsou termíny pseudograf a multigraf synonymem. Pro ostatní je pseudograf multigraf, který může mít smyčky .

Neusměrněný multigraf (hrany bez vlastní identity)

Multigraf G je uspořádaný pár G : = ( V , E ) s

• V set z vrcholů či uzlů ,
• E multiset neuspořádané párů vrcholů, zvaných hrany nebo čáry .

Neusměrněný multigraf (hrany s vlastní identitou)

Multigraf G je uspořádané trojité G : = ( V , E , r ) s

• V set z vrcholů či uzlů ,
• E sada z hran nebo čar ,
• r  : E → {{ x , y }: x , y ∈ V }, přiřazení každé hraně neuspořádané dvojice uzlů koncového bodu.

Někteří autoři povolují, aby multigrafy měly smyčky , tj. Hranu , která k sobě spojuje vrchol, zatímco jiní nazývají tyto pseudografy , čímž si rezervují termín multigraf pro případ bez smyček.

Směrovaný multigraf (hrany bez vlastní identity)

Multidigraph je orientovaný graf , který je přípustné, aby se několik oblouků, tj, oblouky se stejnými zdrojovými a cílovými uzly. Multidigraf G je uspořádaný pár G : = ( V , A ) s

• V sada vrcholů nebo uzlů ,
• Multiset uspořádaných dvojic vrcholů názvem směřuje hrany , oblouky nebo šipky .

Smíšený multigraf G : = ( V , E , ) mohou být definovány stejným způsobem jako smíšené grafu .

Směrovaný multigraf (hrany s vlastní identitou)

Multidigraf nebo toulec G je uspořádaná 4 n-tice G : = ( V , A , s , t ) s

• V set z vrcholů či uzlů ,
• Sada z hran nebo čar ,
• ${\ displaystyle s: A \ rightarrow V}$, přiřazení každé hraně jeho zdrojového uzlu,
• ${\ displaystyle t: A \ rightarrow V}$, přiřazující každému okraji jeho cílový uzel.

Tuto představu lze použít k modelování možných letových spojení nabízených leteckou společností. V tomto případě by multigraf být orientovaný graf s dvojicemi směřujících paralelních hran spojujících měst ukazuje, že je možné létat i na a z těchto míst.

V teorii kategorií lze malou kategorii definovat jako multidigraf (s hranami, které mají svou vlastní identitu), opatřený asociativním kompozičním zákonem a rozlišující samostatnou smyčkou v každém vrcholu, která slouží jako levá a pravá identita pro kompozici. Z tohoto důvodu je v teorii kategorií termín graf standardně chápán jako „multidigraf“ a podkladový multidigraf kategorie se nazývá její podkladový digraf .

Značení

Multigrafy a multidigrafy rovněž podporují pojem označování grafů podobným způsobem. V tomto případě však v terminologii neexistuje jednota.

Definice označených multigrafů a označených multidigrafů jsou podobné a zde definujeme pouze ty druhé.

Definice 1 : Označený multidigraf je označený graf se značenými oblouky.

Formálně: Označený multidigraf G je multigraf se značenými vrcholy a oblouky. Formálně je to 8-tice , kde ${\ displaystyle G = (\ Sigma _ {V}, \ Sigma _ {A}, V, A, s, t, \ ell _ {V}, \ ell _ {A})}$

• V je sada vrcholů a A je sada oblouků.
• ${\ displaystyle \ Sigma _ {V}}$a jsou konečné abecedy dostupných štítků vrcholů a oblouků,${\ displaystyle \ Sigma _ {A}}$
• ${\ displaystyle s \ dvojtečka A \ pravá šipka \ V}$a jsou to dvě mapy označující zdrojový a cílový vrchol oblouku,${\ displaystyle t \ dvojtečka A \ pravá šipka \ V}$
• ${\ displaystyle \ ell _ {V} \ dvojtečka V \ rightarrow \ Sigma _ {V}}$a jsou to dvě mapy popisující označení vrcholů a oblouků.${\ displaystyle \ ell _ {A} \ dvojtečka A \ pravá šipka \ Sigma _ {A}}$

Definice 2 : Označený multidigraf je označený graf s více označenými oblouky, tj. Oblouky se stejnými koncovými vrcholy a se stejným označením oblouku (všimněte si, že tento pojem označeného grafu se liší od pojmu uvedeného v označení grafu článku ).

Viz také

• Multidimenzionální síť
• Glosář pojmů teorie grafů
• Teorie grafů

Poznámky

Reference

• Balakrishnan, VK (1997). Teorie grafů . McGraw-Hill. ISBN  0-07-005489-4 .
• Bollobás, Béla (2002). Teorie moderních grafů . Postgraduální texty z matematiky . 184 . Springer. ISBN  0-387-98488-7 .
• Chartrand, Gary ; Zhang, Ping (2012). První kurz v teorii grafů . Doveru. ISBN  978-0-486-48368-9 .
• Diestel, Reinhard (2010). Teorie grafů . Postgraduální texty z matematiky. 173 (4. vydání). Springer. ISBN  978-3-642-14278-9 .
• Gross, Jonathan L .; Yellen, Jay (1998). Teorie grafů a její aplikace . CRC Press. ISBN  0-8493-3982-0 .
• Gross, Jonathan L .; Yellen, Jay, eds. (2003). Příručka teorie grafů . CRC. ISBN  1-58488-090-2 .
• Harary, Frank (1995). Teorie grafů . Addison Wesley. ISBN  0-201-41033-8 .
• Janson, Svante ; Knuth, Donald E .; Luczak, Tomasz; Pittel, Boris (1993). "Zrození obří komponenty". Náhodné struktury a algoritmy . 4 (3): 231–358. doi : 10,1002 / rsa.3240040303 . ISSN  1042-9832 . MR  1220220 .
• Wilson, Robert A. (2002). Grafy, barvení a čtyřbarevná věta . Oxford Science Publ. ISBN  0-19-851062-4 .
• Zwillinger, Daniel (2002). Standardní matematické tabulky a vzorce CRC (31. vydání). Chapman & Hall / CRC. ISBN  1-58488-291-3 .

externí odkazy

•  Tento článek včlení materiál public domain  z  dokumentu NIST :  Black, Paul E. "Multigraph" . Slovník algoritmů a datových struktur .