A KÖRMENTES ÖSSZEFÜGGŐ GRÁFOKKAL KAPCSOLATOS ALAPVETŐ TÉTELEK ÉS DEFINÍCIÓK.
(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.
Vagy másképp fogalmazva:
Egy körmentes gráfban bármely két pont között legfeljebb egy út fut.
(B) Ha egy gráf két pontja között van séta, akkor van út is,
másrészt:
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”.
Szükségünk lesz a következő két alapvető definícióra, ezeket lépten-nyomon használjuk a gráfelméletben.
Összefüggő gráfnak nevezzük azokat a gráfokat, amelyekben bármely két pont között vezet út.
(B) második állítása alapján rögtön adhatunk egy ALTERNATÍV DEFINÍCIÓT is: egy gráfot akkor nevezünk összefüggőnek, ha van olyan X pontja, amelyből az összes többi ponthoz vezet út.
Fának nevezzük az összefüggő körmentes gráfokat. (Hogy miért így hívják őket, arra hamarosan fény derül.)
Fa például minden út, ezek a „legkiterjedtebb” fák, másrészt a „legsűrűbb” fa az úgynevezett csillag, amelynek van egy telített pontja, és minden él ebből a pontból indul:
(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.
Bizonyítsuk be az (E) állítást!
| TARTALOMJEGYZÉK |