Czy jakieś dwa drzewa rozpinające prostego wykresu zawsze mają jakieś wspólne krawędzie?

24

Wypróbowałem kilka przypadków i okazało się, że dowolne dwa drzewa rozpinające prostego wykresu mają pewne wspólne krawędzie. Mam na myśli, że do tej pory nie znalazłem żadnego kontrprzykładu. Ale nie mogłem tego udowodnić ani obalić. Jak udowodnić lub obalić tę hipotezę?

graphs graph-theory spanning-trees

— Pan Sigma.
źródło

46

Nie, rozważ pełny wykres : $K_4$

Ma następujące drzewa rozpinające się między krawędziami: wprowadź opis zdjęcia tutaj

— Bjørn Kjos-Hanssen
źródło

2

Każde z drzew można uczynić płaskimi, biorąc jedno w kształcie litery a drugie w kształcie literyMożesz uczynić całość płaską, rysując krawędź od górnego prawego wierzchołka do dolnego lewego wierzchołka jako krzywą wychodzącą poza kwadrat.

N

$N$

Z

$Z$

— Kumulacja

@kelalaka Nie potrzebujemy pełnego wykresu, nie (wyobraź sobie, że robię to samo na - chyba że moje przypuszczenia, masz kilka nieużywanych krawędzi, które można usunąć, dzięki czemu nie są już kompletne (ponieważ każdy wierzchołek potrzebuje 2-4 połączonych z nim krawędzi, a każdy wierzchołek w ma 5 dostępnych krawędzi, więc każdy wierzchołek jest przymocowany do co najmniej jednej nieużywanej krawędzi)). jest prawdopodobnie najlepszym przykładem - jest dobrze znany, łatwy do wizualizacji (stosunkowo niewiele krawędzi) i ma bardzo proste drzewa rozpinające.

K_{5}

$K_5$

K_{5}

$K_5$

K_{4}

$K_4$

— Pozew Fund Moniki z dnia

14

Dla bardziej zainteresowanych czytelników istnieją badania nad rozkładem grafu na drzewa rozpinające się między krawędziami .

Na przykład, klasyczne papiery na problem rozkładania wykres w Połączone czynników $n$ wagowych Tutte oraz Edge-rozłącznych drzew rozpinających skończonych wykresów C. St.JA Nash-Williams zapewnia charakterystykę wykresów, który zawiera parami krawędzi-rozłączne obejmujących drzewa. $k$

Na przykład praca Bi-cykliczny rozkład pełnych wykresów na drzewa opinające autorstwa Dalibora Fronceka pokazuje, jak rozkładać pełne wykresy na drzewa izomorficzne . $K_{4k+2}$ ${2k+1}$

Na przykład praca Factorizations z kompletnych wykresów na drzewach opinających o wszystkich możliwych maksymalnych stopniach autorstwa Petr Kovář i Michaela Kubesy pokazuje, jak rozkładać na drzewa opinające o danym maksymalnym stopniu. $K_{2n}$

Możesz wyszukać więcej. Na przykład wyszukiwanie przez Google rozkładu grafu na drzewa rozpinające .

— Apass.Jack
źródło

9

$K_4$

Nie, to nieprawda, że dowolne dwa rozpinające się drzewa wykresu mają wspólne krawędzie.

Rozważ wykres koła:

Możesz zrobić drzewo rozpinające z krawędziami „wewnątrz” pętli i innym z zewnętrznej pętli.

— Gokul
źródło

3

ale zewnętrzna pętla nie dociera do węzła środkowego

— AM

Masz rację, usunę tę odpowiedź, jak druga wystarczy.

— Gokul,

10

Możesz to zmienić, biorąc pętlę wyjściową minus trochę „akordu” plus trochę „promienia” i jego dopełnienia.

— Boboback

Tak. Właściwie widziałem tylko tak. @boboquack

— Mr. Sigma.

3

$K_n$ $n\geq4$

$2$

$K_n$ $n\geq4$ $n\geq4$ $2$

$2$

$2$ $2$
Czy jest jakiś wykres inny niż koło lub koło, ponieważ jego podsgrupa ma rozpinające się drzewa o nieregularnych krawędziach?

— Pan Sigma.
źródło

Odpowiedzi na te i inne pytania znajdują się w cytowanych przeze mnie artykułach. Jeśli jesteś zainteresowany, możesz rzucić okiem.

— Apass.Jack

Dzięki @ Apass.Jack Widziałem twoją odpowiedź. Spojrzę na to.

— Panie Sigma.

1

$K_{2k}$

G_{1} = {(v_{2 i}, v_{2 i + 1}), (v_{2 i}, v_{2 i + 2}), \dots, (v_{2 k - 2}, v_{2 k - 1})},

$G_1 = \{ (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),\dots,(v_{2k-2},v_{2k-1})\},$

G_{2} = {(v_{2 i + 1}, v_{2 i + 2}), (v_{2 i}, v_{2 i}), \dots (v_{2 (k - 1)}, v_{2 (k - 1)})}

$G_2 = \{ (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),\dots(v_{2(k-1)},v_{2(k-1)})\}$

$0\leq i < k$

$n$ $n+1$

— Akumulacja
źródło

0

Jeśli wykres ma pomost (tj. Krawędź, której usunięcie rozłącza wykres), wówczas krawędź ta musi należeć do każdego drzewa opinającego. Intuicyjnie most jest jedyną krawędzią łączącą jego dwa punkty końcowe i dlatego koniecznie należy do każdego połączonego podgrafu.

Z drugiej strony, jeśli krawędź wykresu należy do cyklu, istnieje drzewo rozpinające nie zawierające tej krawędzi.

Tak więc, jeśli każda krawędź wykresu należy do cyklu, żadna krawędź nie jest wspólna dla wszystkich drzew opinających (tzn. Przecięcie zbiorów krawędzi drzew spinających jest zbiorem pustym).

— mo2019
źródło