Gw mau tau Contoh dari Subgraf terinduksi

Di bawah berikut merupakan jenis-jenis subgraf terinduksi yang penting:

Lintasan terinduksi adalah subgraf terinduksi yang merupakan lintasan. Lintasan terpendek di antara sebarang dua buah simpul dalam suatu graf tak berbobot akan selalu merupakan lintasan terinduksi, sebab sebarang sisi tambahan di antara pasangan simpul yang dapat menyebabkannya menjadi tak terinduksi akan menyebabkannya tidak menjadi pendek pula. Hal tersebut berlaku untuk sebaliknya, yang mengatakan setiap lintasan terinduksi merupakan lintasna terpendek dalam distance-hereditary graph.

Siklus terinduksi adalah subgraf terinduksi yang merupakan siklus. Girth dari suatu graf didefinisikan oleh panjang dari siklus terpendeknya yang selalu merupakan siklus terinduksi. Menurut teorema graf sempurna kuat (strong perfect graph theorem), siklus terinduksi beserta komplemennya memainkan peran penting dalam karakterisasi dari graf sempurna.

Clique beserta himpunan bebas adalah subgraf terinduksi yang masing-masing merupakan graf sempurna atau graf tak bersisi.

Matching terinduksi adalah subgraf terinduksi yang merupakan matching.

Lingkungan dari suatu simpul adalah subgraf terinduksi dari semua simpul yang bertetangga dengannya.