SURÁNYI LÁSZLÓ: GRÁFELMÉLET

II. fejezet

Összefüggő és körmentes gráfok, fák,
faváz kereső algoritmusok

Két lehetőség van az olvasásra:

I. lehetőség: a fejezet anyaga két fájlban:

Az egész bevezető (1-16. feladat+ további feladatok)

A további feladatok megoldása egy fájlban

II. lehetőség: A bevezető feladatok lépésenkénti feldolgozása + a további feladatok szövege egy fájlban, de a megoldások külön-külön fájlban:

A) A bevezető feladatok lépésenkénti feldolgozása

Tartalomjegyzék – a fogalom definíciója a fogalom nevére kattintva érhető el:

Séta, út és kör definíciója

Körmentes gráfokra vonatkozó tételek:

Ha egy véges egyszerű gráfban minden pont foka legalább ketttő, akkor van benne kör, II/1, vagy másképp:
ha egy körmentes egyszerű véges gráfban van él, akkor van elsőfokú pontja: II/1’’
Kapcsolódó feladatok: II/39a, II/39b, III/1

n pontú körmentes gráfnak legfeljebb n–1 éle van, II/2

(A) Ha egy (egyszerű) gráfban van két pont, amelyek között fut két különböző út (amelyek akár csak egy élben is különböznek), akkor a gráfban van kör.

(B) Ha egy gráfban van A-t és B-t összekötő út és van B-t és C-t összekötő út, akkor van A-t és C-t összekötő út is. Van olyan A-t C-vel összekötő út is, amely csak e két út pontjait és éleit „használja”.

Összefüggő gráf és fa definíciója, összefüggő gráf két definíciója

(C) Egy gráf pontosan akkor fa (körmentes összefüggő gráf), ha bármely két pontja között pontosan egy út vezet.

(D) Osszuk egy összefüggő gráf pontjait tetszőlegesen két nem üres részre: legyen a két rész A és B. Ekkor biztosan van olyan él a gráfban, amely egy A-beli pontot köt össze egy B-beli ponttal.

(D’) Az állítás meg is fordítható: egy gráf pontosan akkor összefüggő, ha ez bármely két részre osztásánál teljesül.

(E) Egy n pontú fának pontosan n–1 éle van.

Feszítő részgráf, faváz, feszítő fa

Faváz keresés, fa gyökere

(G) Tetszőleges összefüggő gráfnak van faváza.

(F) Egy n pontú összefüggő gráfnak legalább n–1 éle van.

Pontok távolságának definíciója, teljesíti a „háromszögegyenlőtlenséget” II/13

Gráf átmérője, II/47
1-átmérőjű gráfok,
2-átmérőjű gráfok: II/29, lásd még IV/18-20
2-átmérőjű gráfok élszáma: II/49
az átmérő meghatározható polinomiális időben: II/14a

II. eljárás: Szélességi faváz keresése, szélességi faváz definíciója

A szélességi faváz egyszerű tulajdonságai: II/11, II/11a, II/12

Pont apja, pont fia, pont utódja, pont elődje a fában.

Szélességi faváz keresésének számítógépes megvalósításáról

III. eljárás: Mélységi faváz keresése, mélységi faváz definíciója

A mélységi faváz egyszerű tulajdonságai: II/15, II/15a, II/15b, II/15c

Összefüggő komponensek, II/16

Erdő: körmentes gráf, körmentes gráf minden komponense fa

Körmentes gráf élszáma = pontok száma – komponensek száma

(H) Ha egy gráfnak c darab komponense van, akkor van c fából álló feszítő erdeje. Ezért minden n pontú, c komponensből álló gráfnak legalább n – c éle van.

Fák „mini-max” tulajdonsága

Cutpoint definíciója, II/20, II/59

„Vegyük a leghosszabb utat”: II/1, II/59, lásd még: III/1, III/4, III/8, III/9, lásd még IV/67