Více hran - Multiple edges

Více hran spojujících dva vrcholy.

v teorie grafů, více hran (také zvaný rovnoběžné hrany nebo a více hran), jsou v neorientovaném grafu dva nebo více hrany to jsou incident na stejné dva vrcholy, nebo v řízený graf, dvě nebo více hran se stejným vrcholem ocasu a stejným vrcholem hlavy. A jednoduchý graf nemá více hran.

V závislosti na kontextu, a graf mohou být definovány tak, aby buď umožňovaly nebo nepovolovaly přítomnost více hran (často ve shodě s povolením nebo nepovolením) smyčky ):

  • Kde jsou grafy definovány tak, aby dovolit více hran a smyček, graf bez smyček se často nazývá a multigraf.[1]
  • Kde jsou grafy definovány tak, aby zakázat více hran a smyček, multigraf nebo pseudograf je často definován ve smyslu „grafu“, který umět mít smyčky a více hran.[2]

Při zvažování je užitečné například více hran elektrické sítě, z teoretického hlediska grafu.[3] Kromě toho představují základní rozlišovací vlastnost vícerozměrné sítě.

A rovinný graf zůstává rovinný, pokud je hrana přidána mezi dva vrcholy již spojené hranou; přidání více hran tedy zachovává rovinnost.[4]

A dipólový graf je graf se dvěma vrcholy, ve kterém jsou všechny hrany navzájem rovnoběžné.

Poznámky

  1. ^ Například viz Balakrishnan, str. 1, a Gross (2003), s. 1. 4, Zwillinger, str. 220.
  2. ^ Například viz Bollobás, p. 7; Diestel, p. 28; Harary, str. 10.
  3. ^ Bollobás, 39–40.
  4. ^ Gross (1998), p. 308.

Reference

  • Balakrishnan, V. K .; Teorie grafů, McGraw-Hill; 1. vydání (1. února 1997). ISBN  0-07-005489-4.
  • Bollobás, Béla; Teorie moderních grafů, Springer; 1. vydání (12. srpna 2002). ISBN  0-387-98488-7.
  • Diestel, Reinhard; Teorie grafů, Springer; 2. vydání (18. února 2000). ISBN  0-387-98976-5.
  • Gross, Jonathon L a Yellen, Jay; Teorie grafů a její aplikace, CRC Press (30. prosince 1998). ISBN  0-8493-3982-0.
  • Gross, Jonathon L a Yellen, Jay; (eds); Příručka teorie grafů. CRC (29. prosince 2003). ISBN  1-58488-090-2.
  • Zwillinger, Daniel; Standardní matematické tabulky a vzorce CRC, Chapman & Hall / CRC; 31. vydání (27. listopadu 2002). ISBN  1-58488-291-3.