Povezan graf: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja |
Nema sažetka uređivanja |
||
| Redak 4: | Redak 4: | ||
Povezani graf s <math>n</math> vrhova ima barem <math> n - 1 </math> brid, a točno <math> n - 1 </math> brid [[ako i samo ako]] je [[Stablo (teorija grafova)|stablo]].<ref>[https://web.math.pmf.unizg.hr/nastava/matsoft/DobreDZ/2015-16/HTML/TomislavBujanovic/ Prirodoslovno-matematički fakultet u Zagrebu] Tomislav Bujanović: ''Grafovi i njihova svojstva'' (pristupljeno 26. svibnja 2020.)</ref> |
Povezani graf s <math>n</math> vrhova ima barem <math> n - 1 </math> brid, a točno <math> n - 1 </math> brid [[ako i samo ako]] je [[Stablo (teorija grafova)|stablo]].<ref>[https://web.math.pmf.unizg.hr/nastava/matsoft/DobreDZ/2015-16/HTML/TomislavBujanovic/ Prirodoslovno-matematički fakultet u Zagrebu] Tomislav Bujanović: ''Grafovi i njihova svojstva'' (pristupljeno 26. svibnja 2020.)</ref> |
||
Svi [[kritičan graf|kritični grafovi]] su povezani, inače bi svaka komponenta povezanosti imala isti [[kromatski broj]] kao čitav graf.<ref name=Jurasić>[http://www.math.uniri.hr/~ajurasic/D-DEVETO.pdf Odjel za matematiku Sveučilišta u Rijeci] Ana Jurasić: ''Bojenje grafova'', str. 1 (pristupljeno 3. listopada 2020.)</ref> |
|||
== Izvori == |
== Izvori == |
||
Inačica od 3. listopada 2020. u 19:44
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 brid, a točno 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
- ↑ a b 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.)