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 UV(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.