Více hran

Více hran (také nazývané paralelní hrany nebo multi -hrany ) jsou dvě nebo více hran, které se dotýkají stejných dvou vrcholů . Jednoduchý graf nemá více hran.

V závislosti na kontextu může být graf definován s povolením nebo zákazem mít více hran (často spolu s povolením nebo zákazem mít smyčky ):

• Když jsou grafy definovány tak, aby umožňovaly více hran a smyček, grafy bez smyček se často nazývají multigrafy [1] .
• Pokud jsou grafy definovány se zákazem více hran a smyček, jsou multigrafy nebo pseudografy často chápány jako „grafy“, které mohou mít smyčky a více hran [2] .

Vícenásobné hrany jsou užitečné například při uvažování elektrických obvodů z hlediska teorie grafů [3] . Navíc tvoří jádro rozlišovacích vlastností vícerozměrných řetězců .

Rovinný graf zůstane rovinný, pokud přidáte hranu mezi dva vrcholy již spojené hranou. To znamená, že přidání hrany zachová rovinnost [4] .

Dipól je dvouvrcholový graf, ve kterém jsou všechny hrany rovnoběžné.

Poznámky

1. ↑ Viz například Balakrishnan, 1997 , s. 1, Gross, Yellen, 2003 , s. 4, ( Zwillinger 2002 ), s. 220.
2. ↑ Viz například Bollobás str. 7 , Diestel str. 28 , Harary, str. deset.
3. ↑ Bollobás s. 39–;40 .
4. ↑ Gross, Yellen, 1998 , s. 308 .

Literatura

• Balakrishnan VK teorie grafů. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
• Béla Bollobas. Moderní teorie grafů. - Springer, 2002. - ISBN 0-387-98488-7 .
• Reinhard Diestel. teorie grafů. - Springer, 2000. - ISBN 0-387-98976-5 .
  • Reinhard Distel. Teorie grafů. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - ISBN 5-86134-101-X .
• Jonathon L. Gross, Jay Yellen. Teorie grafů a její aplikace. - CRC Press, 1998. - ISBN 0-8493-3982-0 .
• Příručka teorie grafů / Jonathon L. Gross, Jay Yellen. - CRC Press, 2003. - ISBN 1-58488-090-2 .
• Daniel Zwillinger. Standardní matematické tabulky a vzorce CRC. - Chapman & Hall/CRC, 2002. - ISBN 1-58488-291-3 .