UKTG Prednáška 11

Zhrnutie prednášky

Prednáška sa venuje súvislosti grafov nad rámec jednoduchého delenia na súvislé a nesúvislé. Zavádza vrcholovú súvislosť κ(G) ako minimálny počet vrcholov, ktorých odobratím vznikne nesúvislý alebo jednovrcholový graf, a hranovú súvislosť λ(G) ako minimálny počet hrán s rovnakým účinkom. Vysvetľuje pojem k-súvislého grafu a špeciálny prípad kompletných grafov, pre ktoré platí κ(Kn) = n−1. Následne dokazuje tvrdenie, že pre netriviálny graf platí κ(G) ≤ λ(G) ≤ δ(G). Nerovnosť λ ≤ δ plynie z hranového rezu tvoreného hranami incidentnými s vrcholom minimálneho stupňa. Pri nerovnosti κ ≤ λ sa pracuje s minimálnym hranovým rezom L a rozoberajú sa prípady podľa toho, či existuje vrchol neincidentný s hranou rezu.

• - Vrcholová súvislosť κ(G) je minimálny počet vrcholov, ktorých odobratím vznikne nesúvislý alebo jednovrcholový graf.
• - Hranová súvislosť λ(G) je minimálny počet hrán, ktorých odobratím vznikne nesúvislý graf; pri odoberaní vrcholov sa odstraňujú aj incidentné hrany.
• - Pre kompletný graf platí κ(Kn) = n−1, preto definícia pripúšťa aj jednovrcholový výsledný graf; nesúvislý graf má κ = 0.
• - Graf je vrcholovo (hranovo) k-súvislý, ak jeho vrcholová (hranová) súvislosť je aspoň k.
• - Pre netriviálny graf platí κ(G) ≤ λ(G) ≤ δ(G), kde δ(G) je minimálny stupeň.
• - Nerovnosť λ(G) ≤ δ(G) sa dokazuje hranovým rezom z hrán incidentných s vrcholom minimálneho stupňa.
• - Nerovnosť κ(G) ≤ λ(G) sa dokazuje cez minimálny hranový rez L a rozlíšenie prípadu, keď existuje vrchol neincidentný s hranou z L, od prípadu, keď je každý vrchol s takou hranou incidentný.

Zhrnutie pripravené s pomocou AI z prepisu videa.