ÖSSZEFÜGGŐ GRÁF FAVÁZAIRÓL
A feszítő fát adó eljárásban két helyen van választási lehetőségünk: ott, hogy melyik xk-t választjuk és ott, hogy ha már kiválasztottuk, melyik korábban kiválasztott xi szomszédjával kötjük össze.
Az összefüggő gráf
Definíció
Olyan gráf, amelyben bármely két csúcs között létezik út.
Kétszeresen összefüggő gráfok definíciója. Elméletük a kétszeresen élösszefüggő gráfokhoz hasonlóan kidolgozható. Az érdeklődő hallgatók a jegyzetben utána nézhetnek a részleteknek.
összefüggő gráf
Olyan gráf, melyben bármely pontból bármely pontba vezet út. Tehát egy gráf akkor összefüggő, ha egy darabból áll, azaz pontosan egy komponense van.
összefüggő halmaz ...
Legyen véges, összefüggő gráf, ami nem páratlan hosszú kör vagy teljes gráf. Jelölje a maximális fokszámát, pedig a kromatikus számát. Ekkor
Tartalomjegyzék
1 Megjegyzés
2 Bizonyítás
3 Hivatkozások
4 Források ...
Az biztos, hogy összefüggő gráfot keresünk (minden oázisban legyen villany...), azaz olyat, melynek bármely pontjából bármely pontjába eljuthatunk.
Mit nevezünk gráfnak? Mi az n pont teljes gráf? Mi az egyszerű gráf? Mi az összefüggő gráf?
 Lásd még: Összefüggő, Gráf, Definíció, Él, Komponens
  
|
RSS
