Analisis kombinasi algoritma pencarian klik rakus dengan enumerasi sebagian dari simpul grafik

Selamat siang.

Di waktu senggang, saya melakukan sedikit riset.

Dalam teori grafik, algoritma bilangan klik serakah diketahui. Jauh dari biasanya, ia memberikan hasil yang tepat. Di bawah potongan adalah analisis hasil algoritma serakah ketika dikombinasikan dengan enumerasi parsial dari set vertex pada grafik dari set benchmark DIMACS.

Kolom “Paling dikenal” dari tabel 1 menunjukkan ukuran klik maksimum yang diketahui saat ini dari grafik yang ditunjukkan. Kolom "Greedy" menunjukkan ukuran klik maksimum yang ditemukan oleh algoritma serakah. Algoritma serakah memberikan jawaban yang benar hanya dalam 3 kasus dari 35.

Catatan - dalam kode program yang diterapkan, algoritma serakah memilih titik dengan nilai kedekatan tertinggi. Jika beberapa simpul serupa ditemukan, yang pertama ditemukan dipilih. Kita akan memanggil prosedur algoritma serakah Greedy (A), di mana A adalah jumlah array (matriks adjacency) yang digunakan algoritma. Indeks array awal sebagai A0.

, : N , . m, m – . DelNotAdj(m).

Greedy(m). ( ) «1c-Greedy». , , 8 35.

. , DelNotAdj(m). 0, m. mx. Greedy(mx). ( ) «2-Greedy».

3- (3c-Greedy) C500.9 C1000.9 ω(C500.9)=57, ω(C1000.9)=66.

.

Pascal Greedy(A) O(n²), n – . n , 2- – $$$n!/(2!∙(n-2)!)=(n∙(n-1))/2≈n^2$.. $$$n!/(ω(G)!∙(n-ω(G))!)$, ω(G) – () . .

, , ? 1 , .

( 1). O(n), – ω 1 ω(G) – , ω_GR – , .

«Position» 1 . ꞷ(G) , . «» , .

«B» , 2- .

«*» , «», .. 2, 3 . ω. ω_GRCFG.

, , , , . .. , , , 2- .

«» , :

1. 0 «» . ω_GR.
2. «» m, m . m , . ωGR+1.
3. «» mn, m- n- 0. mn , n- m- . ω_GR+2.
4. 3-, 4-,…, y- ω_GR+3, ω_GR+4,…, ω_GR+y .
5. 0 — ω(G).

. «» «B» :

, , ω_GR. ω_GR+1 ω_GR, , K – .

«*» :

«» ω_GR, ω_GR+1, ω_GR+2,…, ω(G) . , , . , ω_GR.

: ω_GR, ω_GR+1, ω_GR+2,… , « » ( ω_GRCDE 1).

:

1. «» ω_GR+y,
ω_GR+y-1, , K – .

.

2. y- ω_GR+y, , .. ω_GR+y=ω_GR+y-1, , ω_GR+y ω(G) .

Jika hal di atas mengulangi pekerjaan orang lain, saya tidak akan menyerah, saya akan senang melihat tautannya. Saya akan lebih senang jika seseorang secara teoritis dapat membuktikan atau menyangkal hipotesis yang diajukan.