Subgraf terinduksi


Dalam teori graf, suatu subgraf terinduksi (bahasa Inggris: induced subgraph) dari suatu graf merupakan graf lain yang terbentuk dari subhimpunan dari simpul graf, dan semua sisi (yang ada di graf aslinya) menghubungkan pasangan simpul di subhimpunan tersebut.

Definisi

Secara formal, misalkan G = ( V , E ) {\displaystyle G=(V,E)} adalah sebarang graf, dan misalkan S ⊂ V {\displaystyle S\subset V} adalah sebarang subhimpunan dari simpul G. Maka subgraf terinduksi G [ S ] {\displaystyle G[S]} merupakan graf yang himpunan simpulnya adalah S {\displaystyle S} serta himpunan sisinya terdiri dari semua sisi di E {\displaystyle E} yang memiliki dua buah simpul ujung di S {\displaystyle S} .[1] Dalam artian, untuk sebarang dua simpul u , v ∈ S {\displaystyle u,v\in S} , u {\displaystyle u} dan v {\displaystyle v} dikatakan bertetanggaan di G [ S ] {\displaystyle G[S]} jika dan hanya jika kedua buah simpul tersebut bertetanggaan di G {\displaystyle G} . Definisi yang sama ini berlaku pula untuk graf tak berarah, graf berarah, dan bahkan multigraf.

Contoh

Masalah ular di sebuah kotak melibatkan lintasan terinduksi terpanjang di graf hiperkubus.

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.[2]
  • 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.[3]
  • 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.

Komputasi

Masalah isomorfisme subgraf terinduksi merupakan sebuah masalah yang terbentuk dari masalah isomorfisme subgraf. Masalah tersebut bertujuan untuk menguji apakah suatu graf dapat ditemukan sebagai suatu subgraf terinduksi dari yang lain. Masalah ini merupakan masalah NP karena meliputi masalah clique sebagai kasus istimewa.[4]

Rujukan

  1. ^ Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, hlm. 3–4, ISBN 9783540261834 
  2. ^ Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 
  3. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070 alt=Dapat diakses gratis, doi:10.4007/annals.2006.164.51, MR 2233847 
  4. ^ Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733