Merekonstruksi Grafik dari Distribusi Derajat

Diberikan distribusi derajat, seberapa cepat kita dapat membuat grafik yang mengikuti distribusi derajat yang diberikan? Sketsa tautan atau algoritme akan bagus. Algoritme harus melaporkan "tidak" jika tidak ada grafik yang dapat dibuat dan salah satu contohnya jika banyak grafik dapat dibuat.

Jika yang Anda maksud adalah bagaimana membuat grafik sederhana seperti itu (tidak ada loop sendiri dan tidak ada tepi paralel), mungkin teorema Havel-Hakimi adalah yang Anda cari. Anda dapat google sendiri, dan Gelar halaman wikipedia (teori grafik) juga membantu.

Jika distribusi derajat diberikan sebagai daftar derajat, maka Anda dapat melakukan yang berikut, diberikan simpul dengan derajat :d 1 , . . . , d $n$$d_1, ... ,d_n$

Buat grafik lengkap pada -vertices. Untuk setiap simpul dalam , pisahkan menjadi salinan. Membagi di sini berarti, membuat sejumlah salinan dengan tepian ke setiap simpul memiliki tepi untuk, tetapi tidak ada tepi ke salinan lain dari . Jika maka cukup hapus simpul. Dalam grafik baru, panggil simpul ini untuk . n v i K n d i v i v i d i = 0 v i j 1 ≤ j ≤ d $K_n$$n$$v_i$$K_n$$d_i$$v_i$$v_i$$d_i = 0$$v_{ij}$$1 \leq j \leq d_i$

Setelah selesai, Anda memiliki grafik yang sangat padat pada simpul; sebut grafik ini . Pilih algoritma favorit Anda untuk pencocokan maksimum (karena grafik begitu padat, Anda mungkin harus menggunakan salah satu algoritma cepat matriks-perkalian berbasis) dan menjalankannya pada . Ini akan mengembalikan nilai cocok . Jika pencocokan tidak sempurna (yaitu jika tidak mencakup semua simpul) maka distribusi gelar Anda tidak mungkin; jadi kembalikan no . H H $N = d_1 + ... + d_n$$H$$H$$M$

Jika Anda memiliki cocok dengan sempurna , maka hapus semua tepi bukan dalam dari , dan kemudian untuk setiap menggabungkan banyak simpul menjadi satu titik . Menggabungkan dua simpul berarti menggabungkan mereka menjadi satu, sehingga simpul yang dihasilkan memiliki tepi ke setiap simpul setidaknya satu dari yang asli memiliki tepi. Panggil grafik yang dihasilkan ; ia memiliki distribusi derajat yang diinginkan.M H 1 ≤ i ≤ n d i v i 1 , . . . , v i d i u i$M$$M$$H$$1 \leq i \leq n$$d_i$$v_{i1}, ... , v_{id_i}$$u_i$$G$

Runtime yang dihasilkan adalah mana adalah konstanta untuk algoritma penggandaan-matriks tercepat (yang pada saat penulisan adalah sekitar ). Dalam hal jumlah simpul dalam grafik yang dihasilkan, dalam kasus terburuk distribusi derajat menjadi padat, kita memiliki .ω 2.373 O ( n 2 ω$O(N^\omega)$$\omega$$2.373$$O(n^{2\omega})$