Grafové operace

Úloha číslo: 3815

Nechť \(k_v(G)\) značí vrcholovou a \(k_e(G)\) hranovou souvislost grafu \(G\).

  • Varianta

    Dokažte, že pro graf \(G\) a hranu \(e \in E(G)\) platí \(k_e(G) - 1 \leq k_e(G - e) \leq k_e(G)\).

  • Varianta

    Dokažte, že pro graf \(G\) a vrchol \(v \in V(G)\) platí \(k_v(G) - 1 \leq k_v(G - v) \).

  • Varianta

    Sestavte graf \(G\), pro nějž platí: \(k_v(G - v) \not\leq k_v(G) \).

  • Varianta

    Dokažte, že smazání hrany nesníží vrcholovou souvislost grafu o více než 1.

    Jinými slovy, že \(k_v(G/e) \ge k_v(G)-1\).

  • Varianta

    Dokažte, že kontrakce hrany nesníží vrcholovou souvislost grafu o více než o 1.

    Jinými slovy, že \(k_v(G/e) \ge k_v(G)-1\).

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze