Masalah komputasi yang sulit pada kelas khusus grafik bipartit

Saya tertarik pada properti dari kelas grafik bipartit mana semua node di X adalah 3-reguler, semua node di Y adalah 2-reguler, dan | X | = | 2 Y / 3 | . Pertama, Apakah ini kelas grafik yang terkenal? Kedua,$G(X \cup Y, E)$$X$$Y$$|X|=|2Y/3|$

Apakah ada contoh masalah komputasi yang tidak bisa diselesaikan terbatas pada kelas grafik bipartit ini?

Diberikan grafik 3-reguler Anda dapat membuat grafik bipartit G ′ dengan properti yang diperlukan memilih X = V dan Y = E dan untuk setiap sisi e k = ( u i , u j ) ∈ E add ujung-ujungnya ( u i , e k ) , ( e k , u j$G = \{V,E\}$$G'$$X = V$$Y = E$$e_k = (u_i,u_j) \in E$$(u_i, e_k), (e_k, u_j)$. Jadi saya pikir Anda dapat menemukan beberapa masalah sulit mulai dari masalah sulit pada grafik 3-reguler.

Misalnya SUBGRAPH ISOMORFISME adalah NP-hard untuk kelas grafik Anda.

$G$$G' = \{X \cup Y, E'\}$$H'$$2|V|$$G'$$H'$$G$

$I(G)$$G$

$G$$k$$G$$k$$G$$k$$G$

Ada kemungkinan bahwa masalah bandwidth untuk grafik ini adalah NP-complete, karena ini NP-complete untuk pohon di mana setiap vertex memiliki derajat paling banyak tiga. (Sumber: masalah GT40 di Garey dan Johnson untuk grafik umum; untuk pohon derajat rendah, Garey, Graham, Johnson dan Knuth, "Hasil kompleksitas untuk meminimalkan bandwidth", SIAM J. Appl. Math. 34: 477-495; Citeseer . )

$G$$k$$I(G)$$k$$I(K_{1,3})$$I(K_{1,3})$$I(G)$