Apakah kelas grafik berikut dikenal dalam literatur? Kelas grafik diparameterisasi dengan bilangan bulat positif dan dan berisi setiap grafik sedemikian rupa sehingga untuk setiap simpul , subgraf diinduksi pada semua simpul pada jarak paling banyak dari di memiliki treewidth paling banyak...
Saya tertarik pada properti grafik berarah acak dengan tingkat out-fixddd . Saya membayangkan model grafik acak di mana setiap simpul memilih tetangga d (katakanlah, dengan penggantian) uar Pertanyaan : Adakah yang diketahui tentang distribusi stasioner dan waktu pencampuran jalan acak pada...
Mari kita mengatakan bahwa grafik adalah -connected jika penghapusan setiap simpul dan setiap tepi dari daun selalu graf terhubung. Misalnya, grafik -connect, sesuai dengan definisi standar, adalah -connected, sesuai dengan definisi baru. Apakah ada algoritma polinomial-waktu untuk memutuskan...
Saat mencari Sistem informasi pada Kelas Grafik dan Inklusi mereka , saya menemukan beberapa kelas grafik yang masalah Siklus Hamiltonian adalah NP-lengkap sedangkan kompleksitas masalah Jalur Hamiltonian TIDAK diketahui. Beberapa kelas tersebut adalah grafik derajat 3 maksimum bipartit, grafik...
Sebuah perpanjangan linear dari poset P adalah pesanan linear pada unsur-unsur P , sehingga x ≤ y di P menyiratkan x ≤ y di L untuk semua x , y ∈ P .LLLPP\mathcal{P}PP\mathcal{P}x≤yx≤yx \leq yPP\mathcal{P}x≤yx≤yx \leq yLLLx,y∈Px,y∈Px,y\in\mathcal{P} Sebuah grafik ekstensi linear adalah grafik pada...
Diberikan jalan acak pada grafik, waktu sampul adalah yang pertama (jumlah langkah yang diharapkan) yang setiap titik telah tekan (tertutup) oleh jalan. Untuk grafik yang tidak diarahkan yang terhubung, waktu tutup diketahui dibatasi oleh . Ada digraf yang sangat terhubung dengan eksponensial waktu...
Saya membaca tentang kelas graf yang Graph isomorfisma ( ) dalam P . Salah satu kasus tersebut adalah grafik valensi terikat (maksimum lebih dari derajat setiap simpul) seperti yang dijelaskan di sini . Tapi saya merasa terlalu abstrak. Saya akan berterima kasih jika ada yang bisa menyarankan saya...
Grafik planar memiliki genus nol. Grafik yang dapat disematkan pada torus memiliki genus paling banyak 1. Pertanyaan saya sederhana: Apakah ada masalah yang dapat dipecahkan secara polinomi pada grafik planar tetapi NP-hard pada grafik genus satu? Lebih umum apakah ada masalah yang secara...
(juga bertanya di sini , tidak ada balasan) A -quantum expander adalah distribusi atas kelompok kesatuan dengan properti yang: a) , b) , di mana adalah ukuran Haar. Jika alih-alih distribusi pada unitari kami mempertimbangkan distribusi atas matriks permutasi, tidak sulit untuk melihat bahwa kami...
Pertanyaan ini mirip dengan salah satu pertanyaan saya sebelumnya. Hal ini diketahui bahwa adalah minor dilarang untuk grafik dari treewidth paling t .Kt + 2Kt+2K_{t+2}ttt Adakah keluarga yang dibangun dengan baik, parameter, dan tak terbatas grafik (selain grafik lengkap dan grafik kisi) yang...
Saya tidak memiliki pengetahuan di bidang teori kompleksitas yang melibatkan kelompok, jadi saya minta maaf jika ini adalah hasil yang diketahui. Pertanyaan 1. Biarkan menjadi grafik pesanan sederhana yang tidak diarahkan n . Apa kompleksitas komputasi (dalam hal n ) untuk menentukan apakah G...
Saya tertarik dengan masalah ini: Diberi grafik tidak terarah , Apakah ada partisi ke dalam grafik dan sedemikian sehingga dan isomorfis?G G 1 ( E 1 , V 1 ) G 2 ( E 2 , V 2 ) G 1 G 2G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Di sini dipartisi...
Dalam [1], Turan menunjukkan bahwa sensitivitas (disebut "kompleksitas kritis" di kertas) properti grafik benar-benar lebih besar dari manamadalah jumlah simpul dalam grafik. Dia melanjutkan dengan dugaan bahwa setiap properti grafik non-sepele memiliki sensitivitas≥m-1. Dia menyebutkan bahwa ini...
Saya mencoba untuk mengetahui bagaimana Path Graph menurut Algoritma Eppstein dalam makalah ini bekerja dan bagaimana saya dapat merekonstruksi jalur terpendek dari ke dengan konstruksi tumpukan yang sesuai .P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Sejauh ini: out(v)out(v)out(v) berisi semua tepi...
Setiap planar , masing-masing, outerplanar graph memenuhi , masing-masing, , untuk setiap subgraf dari . Juga, grafik planar (luar) dapat dikenali dalam waktu polinomial.| E ′ | ≤ 3 | V ′ | - 6 | E ′ | ≤ 2 | V ′ | - 3 G ′ = ( V ′ , E ′ ) GG = ( V, E)G=(V,E)G=(V,E)| E′| ≤3 | V′|...
Apa hasil deterministik terbaik untuk mempertahankan penutupan transitif dinamis dalam grafik terarah dengan hanya penyisipan tepi? Saya membaca beberapa makalah tentang masalah penutupan transitif dinamis dengan kedua penyisipan tepi dan penghapusan. Namun, apakah ada algoritma yang lebih baik...
Maaf, jika ini adalah pertanyaan naif, tapi saya tidak dapat menemukan pembenaran di salah satu buku teks utama seperti Bondy-Murty, Diestel atau Barat. Grafik sempurna memiliki banyak properti yang indah, tetapi apa alasan mereka disebut sempurna? Atau itu hanya preferensi estetika oleh...
Seperti diketahui, dekomposisi pohon pada grafik terdiri dari pohon dengan kantung terkait untuk setiap simpul , yang memenuhi kondisi berikut:T T v ⊆ V ( G ) v ∈ V ( T )GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Setiap simpul dari terjadi di beberapa kantong T .GGGTTT Untuk...
Kita tahu bahwa kita dapat mewakili grafik planar apa pun dengan seperangkat lingkaran di pesawat, yang dikenal sebagai grafik koin . Setiap lingkaran mewakili sebuah simpul dan ada sebuah tepi di antara dua simpul jika dan hanya jika lingkaran "mencium" pada batasnya. Misalkan sebaliknya kita...
Kami berasumsi bahwa . Maka fakta berikut diketahui:G∈G(n,p),p=lnn+lnlnn+c(n)nG∈G(n,p),p=lnn+lnlnn+c(n)nG\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n} Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)Pr[G has a Hamiltonian...