Összefüggőség, alapfogalmak

Lemma: Az ``két éldiszjunkt úttal való összeköthetőség'' reláció (jelölésben ^) ekvivalenciareláció egy gráf csúcsainak halmazán.

A két lemma a csúcshalmaz egy-egy osztályozását definiálja. A második osztályozás az első finomítása (a második osztályozás két csúcs ugyanabba az osztályba esése az első osztályozásnál is azonos osztályhoz tartozást jelent).

A két osztályozásnak van egy közös vonása. Vegyük egy osztály két elemét, u-t és v-t. Az azonos osztályhoz tartozást a definíció alapján értelmezhetjük: az első osztályozás esetén ez azt jelenti, hogy a két elem (u és v) között van G-beli (az alapgráfbeli) út. Ezen út minden csúcsa u-val is ekvivelens, tehát az egy osztályhoz tartozást bizonyító út teljes egészében az osztályon belül halad. Azaz egy osztály által feszített részgráf olyan, hogy bármely két pontja a megfelelő relációban áll egymással. A második reláció esetén hasonlóan érvelhetünk, de a két éldiszjunkt út létezése helyett egy másik megfogalmazással élve érvelésünk transzparensebb lesz: u^v akkor és csak akkor, ha van egy zárt vonal, amely mindkét csúcson áthalad. Nyilvánvaló, hogy egy zárt vonal bármely két csúcsa relációban áll. Azaz az egy osztályhoz tartozást bizonyító zárt vonal teljes egészében az osztályon belül halad, az osztály által feszített részgráf bármely két pontja relációban áll.

Lemma: Az ~ reláció osztályozása a következő tulajdonságokkal rendelkezik

• Az osztályok által feszített részgráfok olyanok, hogy bármely két csúcsuk között van út.
• A különböző osztályok között nem halad él.

Lemma: Az ^ reláció osztályozása a következő tulajdonságokkal rendelkezik

• Az osztályok által feszített részgráfok olyanok, hogy bármely két csúcsuk koz;ött van két éldiszjunkt út.
• Az osztályok között haladó élek leírásához vezessünk be egy segédgráfot: a csúcsok az osztályok lesznek, az élek azon élek, amelyek különböző osztályok közötti csúcsokat kötnek össze, illeszkedés pedig az lesz, hogy egy e=xy él az x és y osztályát reprezentáló két csúcsra illeszkedik. (Definíció szerint segédgráfunk nem tartalmaz hurokélt.) Ezen segédgráf nem tartalmaz kört.

Definíció: Egy gráf összefüggő, ha bármely két pontja között van út.

Definíció: Egy gráfra az ~ osztályai által feszített részgráfokat a gráf komponenseinek nevezzük.

Definíció: Egy gráf kétszeresen élösszefüggő, ha bármely két pontja között van két éldiszjunkt út.

Definíció: Egy gráfra az ^ osztályai által feszített részgráfokat a gráf kétszeresen élösszefüggő komponenseinek nevezzük.

Megjegyezzük, hogy a fenti segédgráf komponensei ^ osztályait sorolják osztályokba. Az egy osztályba került ösztályok uniója az eredeti gráf egy komponensének csúcshalmazát, azaz ~ egy osztályát adja.

Lemma: Az ``azonosnak lenni vagy egy körre esni '' reláció (jelölésben o) ekvivalenciareláció egy gráf éleinek halmazán.

A gráf éleit o ekvivalenciaosztályokba sorolja. Minden osztály feszít egy részgráfot (az osztály élei által lefedett csúcsok és az osztály élei által alkotott részgráfot).

Lemma: Egy egyszerű gráf esetén az o reláció élosztályai által feszített részgráfokról a következőket állíthatjuk

• Az élosztályok által feszített részgráfok vagy két pont egyetlen éllel összekötve vagy legalább három pontúak és bármely két élük egy körre esik.
• A részgráfok egymáshoz való viszonyának leírásához egy segédgráfot vezetünk be: A csúcsok az osztályok által feszített részgráfok (R-csúcsok), illetve azok a csúcsok lesznek, amelyek több részgráfhoz is hozzártartoznak (C-csúcsok). Minden él R- és C-csúcsok között halad (páros grafot írunk le). Egy részgráfnak megfelelő r csúcs és egy c csúcs akkor lesz összekötött, ha c az r részgráf csúcsa. Ez a segéd gráf nem tartalmaz kört.

Definíció: Egy gráf kétszeresen (pont)összefüggő, ha összefüggő és bármely két éle egy körön van, továbbá legalább három pontja van.

Definíció: Egy gráfra az o élosztályai által feszített, legalább három pontú részgráfokat a gráf kétszeresen összefüggő komponenseinek nevezzük.