Povezan graf

Povezan graf, vrsta grafa u teoriji grafova. Ako postoji put među bilo kojim dvama vrhovima graf je povezan, a u suprotnom je nepovezan.^[1]

Ako je graf povezan i neusmjeren, razapinjuće stablo u tom grafu je podgraf koji je stablo i razapinje taj graf. Graf je stablom ako su svaka dva vrha u njemu povezana točno jednim putem. Stablo je svaki povezani graf bez ciklusa. ^[1]

Povezani graf s $n$ vrhova ima barem $n-1$ brid, a točno $n-1$ brid ako i samo ako je stablo.^[2]

Svi kritični grafovi su povezani, inače bi svaka komponenta povezanosti imala isti kromatski broj kao čitav graf.^[3]

Izvori

↑ ^1,0 ^1,1 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)
↑ Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)
↑ Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova, str. 1 (pristupljeno 3. listopada 2020.)

[E-math-1] 1,0 ^1,1 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)

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

[Jurasić-3] Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova, str. 1 (pristupljeno 3. listopada 2020.)

[1]

[2]

[3]