10.3 Részgráfok és indukált gráfok
A H gráf a G gráf részgráfja,
ha és
.
Legyen és
. A H = G - v gráf a v csúcs törlésével áll elő G-ből, ha
és E(H ) a G azon éleit tartalmazza, amelyek nem
illeszkednek v-re. Ha
, akkor H = G - e a G gráfból az e él kitörlésével áll elő, és H a G-nek egy olyan
részgráfja, amelyre V(H ) = V(G) és E(H ) = E(G) - {e}. A következő ábrán példát mutatunk a csúcs és
az él törlésére.
2. ábra. Csúcs és él törlése egy gráfban.
Ha u és v a G nem szomszédos
csúcsai, akkor G + f, ahol f
= uv, jelöli azt a gráfot, amelynek csúcshalmaza V(G) és
élhalmaza . Ezért G
G +
f.
Ha H a G gráf részgráfja, és H rendje megegyezik G rendjével, akkor H -t G feszítő részgráfjának nevezzük. A 2. ábrán a G-e gráf a G gráf egy feszítő részgráfja.
Megjegyzés.
Az éltörlés definíciójából azonnal következik, hogy ha a H a G ráfnak olyan részgráfja, amelyet G-ből éltörlésekkel hoztunk létre - azaz nem törölünk csúcsokat - akkor a H a G gráfnak mindig a feszítő részgráfja lesz.
Ha U a V(G) egy részhalmaz, akkor az <U> a G-nek egy olyan -
az U csúcsai által - indukált részgráfja,
amelynek csúcshalmaza és
élhalmaza minden olyan élet tartalmaz G-ből, amely illeszkedik az U két elemére. A 2. ábrán a G-v
gráf a G gráfnak egy olyan indukált
részgráfja, amelyben U a G megmaradt csúcsait tartalmazza.
Megjegyzés.
Az csúcstörlés definíciójából azonnal következik, hogy ha a H a G ráfnak olyan részgráfja, amelyet G-ből csúcstörlésekkel hoztunk létre, akkor a H a G gráfnak mindig indukált részgráfja lesz.
Két gráfot akkor nevezünk izomorfnak, ha van a két gráf csúcshalmazai között olyan kölcsönes egyértelmű (bijektív) leképezés, amely megőrzi a csúcsok szomszédsági relációját.