Sub Graf

Konsep subgraf sama dengan konsep himpunan bagian. Dalam teori himpunan, himpunan A dikatakan merupakan himpunan bagian B bila dan hanya bila setiap anggota A merupakan anggota B. Karena graf merupakan himpunan yang terdiri dari titik dan garis maka H dikatakan subgraf G jika semua titik dan garis H juga merupakan titik dan garis dalam G. Secara formal, subgraf didefinisikan seperti di bawah ini :

Misalkan G adalah suatu graf. Graf H dikatakan subgraf G bila dan hanya bila:

• V (H) ⊆ V (G)
• E (H) ⊆ E (G)

Setiap garis dalam H mempunyai titik ujung yang sama dengan garis tersebut dalam G.

Dari definisi di atas, ada beberapa hal yang dapat diturunkan :—Sebuah titik dalam G merupakan subgraf G
—Setiap graf merupakan subgraf dari dirinya sendiri
—Dalam subgraf berlaku sifat transitif : Jika H adalah subgraf G dan G adalah subgraf K, maka H adalah subgraf K. Dalam graf Gambar 15 (a) - (b) di bawah ini

                                 

 

:H merupakan SubGraf G:

:H bukan merupakan SubGraf dari G;