Pertimbangkan masalah berikut:
Input: grafik sederhana (tidak terarah) .
Pertanyaan: Apakah ada orientasi memuaskan properti yang untuk setiap paling banyak ada satu (diarahkan) - berjalan?s , t ∈ V s t
Ini dapat secara ekuivalen diungkapkan sebagai:
Input: grafik sederhana (tidak terarah) .
Pertanyaan: Apakah ada orientasi asiklik memuaskan properti yang untuk setiap paling banyak terdapat satu ( ) jalur - ?s , t ∈ Vt
Apa kelas grafik yang jawabannya adalah "ya"? Bisakah masalah ini diselesaikan dalam waktu polinomial?
Beberapa pengamatan:
- Jika grafiknya adalah bipartit, maka jawabannya adalah "ya."
- Jika grafik memiliki segitiga, maka jawabannya adalah "tidak."
Pengamatan pertama mengikuti dengan mengorientasikan tepi dari satu partisi ke yang lain. Pengamatan kedua mudah untuk diperiksa. Ini membawa saya ke dua tebakan yang salah:
- Jawabannya adalah "ya" jika dan hanya jika grafiknya adalah bipartit. (counterexample: the 5-cycle)
- Jawabannya adalah "ya" jika dan hanya jika grafiknya bebas segitiga (berlawanan dengan contoh: produk kartesian tepi dengan siklus 5)
sumber