Tingkat minimum "grafik pohon"

Diberikan grafik , tentukan grafik pohon sebagai grafik yang simpulnya adalah pohon spanning , dan ada tepi antara dua pohon jika satu dapat diperoleh dari yang lain dengan mengganti satu tepi. Yaitu ada tepi jika ada dua sisi sedemikian sehingga . $G$ $T(G)$ $G$ $(T_1, T_2)$ $x, y \in G$ $T_1 - x = T_2 - y$

Pertanyaan saya adalah ini: adakah batas bawah atau atas non-trivial pada derajat vertex dengan derajat minimum dalam ? $T(G)$

Catatan: Saya mengedit pertanyaan (baris terakhir) sedikit untuk membuatnya kurang ambigu.

graph-theory tree corwin
sumber

Definisi Anda tentang keunggulan tidak masuk akal. Apakah maksud Anda "ada tepi antara

dan

jika ada dua sisi

sedemikian sehingga

T_{1}

$T_1$

T_{2}

$T_2$

x, y \in G

$x, y \in G$

T_{1} - x + y = T_{2}

$T_1 - x + y = T_2$

Tyson Williams

Ya, maaf saya maksudkan tepi.

corwin

Jika

adalah pohon, grafik pohonnya

adalah simpul tunggal dengan derajat 0. Di sisi lain, jika

adalah grafik lengkap, setiap simpul di

memiliki derajat

. Apa sebenarnya yang Anda maksud dengan "non-sepele"?

G

$G$

T (G)

$T(G)$

G

$G$

T (G)

$T(G)$

Θ (n^{2})

$\Theta(n^2)$

Jeffε

G

$G$

Θ (n^{2})

$\Theta(n^2)$

S

$S$

T

$T$

| S | \cdot | T |

$|S|\cdot|T|$

Θ (n^{3})

$\Theta(n^3)$

Jawaban:

$G$ $n$ $m$ $T$ $G$ $m-n+1$ $T$ $T$ $G$ $2(m-n+1)$ $T$ $2(m-n+1)$

$G$ $v$ $T$ $v$ $T$ $T$ $T$ $2(m-n+1)$

$G$ $g$ $T$ $g$ $(g-1)(m-n+1)$

Namun, menemukan tingkat minimum grafik pohon untuk grafik yang diberikan secara sewenang-wenang (ekuivalen, menemukan pohon rentang yang meminimalkan jumlah panjang siklus yang disebabkan oleh tepi non-pohon) adalah lengkap-NP: lihat Deo, Prabhu, dan Krishnamoorthy, "Algoritma untuk Menghasilkan Siklus Fundamental dalam Grafik", ACM TOMS 1982 . Jadi menemukan batasan seperti ini yang ketat untuk semua grafik tampaknya tidak mungkin.

David Eppstein
sumber

Terima kasih atas jawabannya. Bisakah kita menemukan batas atas ketat yang benar untuk semua grafik?

corwin

n

$n$

m

$m$