Potpun graf

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži
Potpuni graf
Primjer potpunog grafa s 5 vrhova

Potpun graf je jednostavan graf u kojem je svaki par vrhova spojen bridom.

U potpunom grafu vrijedi:[1]

  • [math]\displaystyle{ (\forall u,v \in V)(u \neq v \implies (u,v) \in E) }[/math]
  • Tada je broj bridova u potpunom grafu [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]

Suprotno od potpunog grafa je prazan graf u kojem ni jedan vrh nije spojen ni s jednim drugim vrhom u grafu.

Potpun bipartitan graf - Jednostavan bipartitan graf s biparticijom (X, Y ) u kojima je svaki vrh iz X spojen sa svakim vrhom iz Y.

Izvori

  1. Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)