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 vrhova ima barem Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n - 1 } brid, a točno Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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.)