I. MEGOLDÁS:
Nyilvánvaló, hogy ha egy gráfban van elsőfokú pont, akkor az nem cutpoint. Az elsőfokú pont bármely favázban is elsőfokú lesz, tehát végpont lesz. Ha az összefüggő G gráfban nincs elsőfokú pont, de találunk olyan x pontot, amely hasonlóan „végpont”-jellegű, akkor x elhagyásával nem fog „szétesni” a G gráf, így G-ben is van olyan pont, amely nem cutpoint. Erre már ismerünk egy módszert: vegyük a G gráf leghosszabb útját vagy azok közül egyet, legyen ez P, és legyen x a P út egyik végpontja. Tudjuk, hogy x minden szomszédja az úton van: ha például y olyan szomszédja volna x-nek, amely nincs rajta P-n, akkor P-t meghosszabbíthatnánk az xy éllel, tehát P nem volna leghosszabb út. Most belátjuk a következő
Megmutatjuk, hogy x pontosan akkor cutpoint, ha van két olyan szomszédja, u és v, amelyek között az uxv úton kívül nem megy út a gráfban.
Nyilvánvaló, hogy ha u és v két ilyen szomszédja x-nek, akkor x elhagyásával ők különböző komponensekbe kerülnek, tehát a G–x gráf valóban nem összefüggő, x valóban cutpoint. Ha pedig x cutpoint, akkor G–x több komponensre esik szét, így lesz olyan y és z pont, amelyek között G–x-ben nem megy út. Másrészt G összefüggő, tehát G-ben megy közöttük út, jelöljük ezt R-rel. Az R út ezek szerint biztosan tartalmazza x-et. Legyen ezen az úton x két szomszédja u és v. Az R út tehát így néz ki: z…uxv…y. Ha u és v között a gráfban menne az uxv útvonaltól különböző út, akkor azt beírva uxv helyett kapnánk egy olyan sétát z és y között, amely nem tartalmazza x-et. Vagyis y és z között lenne séta G–x-ben. De akkor út is lenne közöttük G–x-ben, ami ellentmond az y-ra és z-re tett kikötésünknek. Ezzel beláttuk, hogy u és v valóban olyan szomszédai x-nek, amelyek között uxv az egyetlen út G-ben.
Segédtételünkből már következik, hogy x nem cutpoint. Láttuk ugyanis, hogy x minden szomszédja az úton van. De ebből következik, hogy bármely két szomszédjához van olyan út, amely „elkerüli” x-et: tudniillik a P útnak az a szakasza, amely e két szomszédját összeköti. Ez viszont a segédtételünk szerint azt jelenti, hogy x nem lehet cutpoint. Ezzel beláttuk, hogy minden összefüggő gráfnak van olyan pontja, amely nem cutpoint.
II. MEGOLDÁS:A faváz segítségével sokkal hamarabb is célhoz érhetünk:
Vegyük a gráf egy favázát és annak egy elsőfokú (vég-)pontját. Ha ezt elhagyjuk a fából, a fa továbbra is összefüggő marad, s akkor az egész maradó gráf is nyilván összefüggő marad, hiszen van faváza.
Mindkét bizonyítás rögtön azt is adja, hogy tetszőleges összefüggő gráfban legalább két pont van, amely nem cutpoint. Mindkét bizonyításból kijön az is, hogy pontosan akkor van csak két cutpoint, ha a gráf egyetlen útból áll (ha minden faváza egyetlen út).
| TARTALOMJEGYZÉK |