Részgráf

Részgráf hurokél-nélküli gráfokban

R hurokél-nélküli gráf egy G hurokél-nélküli gráf részgráfja, a R megkapható G-ből pontok és élek elhagyásával.

3. Felbontás teljes részgráfokra
Előző
Teljes gráfok felbontásairól
Következő ...

Részgráf
Feszített részgráf fogalma
Szomszéd: egy pont szomszédai azok a pontok, amelyekkel él köti össze
Telített pont: olyan pont, amely a gráf minden más pontjával össze van kötve ...

Részgráfok
A gráf komponenseinek kiválasztása - mélységi keresés - cikk
A gráf komponenseinek kiválasztása - szélességi keresés - cikk ...

Egy H részgráf feszített részgráfja G-nek, ha H bármely két csúcsára igaz, hogy szomszédosak H-ban akkor és csak akkor, ha szomszédosak G-ben.

Van tehát egy 7 csúcsú 15 élű részgráfunk! Ekkor azonban ebben a részgráfban van teljes hármas. És mivel a teljes hármas minden csúcsa össze van kötve a piros csúccsal, eredeti gráfunkban biztos, hogy van teljes négyes.

Lásd még: Gráf, Összefüggő, Él, Bizonyítás, Definíció