Multigraf

Iz Wikipedije, proste enciklopedije
(Preusmerjeno s strani Psevdograf)
Jump to navigation Jump to search
Multigraf z večkratnimi povezavami (rdeče) in zankami (modro).
Vsi ne dopuščajo zank v multigrafih.

Multigraf je v matematiki graf, ki lahko ima večkratne povezave (ali vzporedne povezave), ki potekajo med posameznimi točkami. To pomeni, da sta dve točki povezani z več kot samo eno povezavo.

Multigraf je urejeni par , kjer je:

Nekateri ne ločujejo pojma multigraf in psevdograf. Za druge je psevdograf multigraf z zankami.

Posebna oblika je multidigraf, ki je usmerjeni graf, ki lahko vsebuje večkratne povezave od točke nazaj do iste točke (zanka). Multidigraf je urejeni par za katerega velja:

  • je množica točk
  • je večkratna množica parov točk, ki se imenujejo usmerjene povezave ali loki ali puščice.

Zunanje povezave[uredi | uredi kodo]