Razlika između inačica stranice »Povezan graf«
Izvor: Hrvatska internetska enciklopedija
(Bot: Automatski unos stranica) |
m (bnz) |
||
| Redak 1: | Redak 1: | ||
Povezan graf''', vrsta [[graf (teorija grafova)|grafa]] u [[teorija grafova|teoriji grafova]]. Ako postoji [[put (teorija grafova)|put]] među bilo kojim dvama [[vrh (teorija grafova)|vrhovima]] graf je povezan, a u suprotnom je [[nepovezan graf|nepovezan]].<ref name="E-math"/> | |||
Ako je graf povezan i [[neusmjeren graf|neusmjeren]], [[razapinjuće stablo]] u tom grafu je [[podgraf]] koji je [[stablo (teorija grafova)|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 [[ciklus (teorija grafova)|ciklusa]]. <ref name="E-math">[http://e.math.hr/math_e_article/br14/fosner_kramberger 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.)</ref> | Ako je graf povezan i [[neusmjeren graf|neusmjeren]], [[razapinjuće stablo]] u tom grafu je [[podgraf]] koji je [[stablo (teorija grafova)|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 [[ciklus (teorija grafova)|ciklusa]]. <ref name="E-math">[http://e.math.hr/math_e_article/br14/fosner_kramberger 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.)</ref> | ||
Trenutačna izmjena od 03:46, 24. ožujka 2022.
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 [math]\displaystyle{ n }[/math] vrhova ima barem [math]\displaystyle{ n - 1 }[/math] brid, a točno [math]\displaystyle{ n - 1 }[/math] 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.)