Odwołanie się do klasy wykresów, które zachowują odległości subgrafów przy zamówieniu

12

Powiedzmy, że wykres ma właściwość jeśli jego wierzchołki można uporządkować w taki sposób, że wykres indukowany przez wierzchołki ma $G$ $M$ $v_1, v_2, \ldots v_n$ $H_i$ $\{v_1, \ldots, v_i\}$ dla wszystkich . Innymi słowy, dodanie następnego wierzchołka w naszym porządku nie wpływa na metrykę odległości bieżącego wykresu. $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ $j,k \leq i$

Przykładem takiego wykresu jest regularna siatka . $n \times n$

Czy ta właściwość lub klasa grafów ma nazwę? Czy zostały zbadane?

reference-request graph-theory mich
źródło

Prostym przykładem wykresu, który ma nie mają tej właściwości jest

-cycle dla

. To dlatego, że dla każdej kolejności, że subgraphs

mają być połączone, a więc w czasie

,

to linia długości

, a więc niektóre dwa wierzchołki są odległość

od siebie.

k

$k$

k \geq 5

$k \ge 5$

H_{i}

$H_i$

i = ⌊ k / 2 ⌋ + 2 < k

$i = \lfloor k/2 \rfloor +2 < k$

H_{i}

$H_i$

i - 1

$i-1$

i - 1 > ⌊ k / 2 ⌋

$i-1 > \lfloor k/2 \rfloor$

Andrew Morgan

Z drugiej strony, naturalnym kandydatem do znalezienia dobrego porządku

jest wykonanie BFS z dowolnego wyboru

. Przeglądając

jak drzewo BFS z niektórych dodatkowych krawędzi, wydaje się, że jedyną przeszkodą do posiadania własności

jest, aby istniała coś „jak”

-cycle dla

w

. Przez „jak” rozumiem, że istnieje

motocykl

v_{1}, \dots, v_{n}

$v_1, \ldots, v_n$

v_{1}

$v_1$

G

$G$

M

$M$

k

$k$

k \geq 5

$k \ge 5$

G

$G$

k

$k$

przy

tak aby

w

. Jeśli nazwiemy taki cykl „minimalnym”, to czy prawdą jest, że właściwość

jest równoważna nieistnieniu minimalnych cykli o długości co najmniej 5?

v_{1}, \dots, v_{k}, v_{k + 1} = v_{1}

$v_1, \ldots, v_k, v_{k+1}=v_1$

k \geq 5

$k \ge 5$

d (v_{i}, v_{j}) = | i - j |

$d(v_i,v_j) = |i-j|$

G

$G$

M

$M$

Andrew Morgan,

1

k

$k$

8

Wygląda na to, że pytasz o grafy, które akceptują porządek eliminacji zachowujący odległość, który tworzy klasę wykresów zbadanych w tym artykule:

http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec

JimN
źródło

2

Dostępny również bezpłatnie na stronie autora: lif-sud.univ-mrs.fr/%7Echepoi/dpo.ps

Florent Foucaud

8

Nie mam odpowiedź dla całej klasy grafów, ale trzy podklasy grafów, które mają tę właściwość są distance-dziedziczna wykresy , cięciwowe wykresy , a mediana wykresy .

$v_1$

Wykresy akordowe to wykresy, które mają uporządkowanie z tą właściwością, że każdy kolejny wierzchołek po dodaniu ma klikę dla swoich sąsiadów. To uporządkowanie oczywiście zachowuje odległość.

Podobnie wykresy środkowe (w tym przykład siatki) mają tę właściwość, że dla dowolnej kolejności pierwszego rzędu każdy wierzchołek ma sąsiedztwo hipersześcianu w momencie dodawania. (Patrz strony 76–77 Eppstein i in., „Media Theory”, Springer, 2008). Znów ta właściwość oznacza, że dodanie nie może zmienić odległości między poprzednimi wierzchołkami.

Istnieje klasa wykresów, dla których nie znam nazwy, uogólniająca zarówno wykresy akordowe, jak i dziedziczne, które można rozpoznać w czasie wielomianowym i które mają Twoją własność. Są to połączone wykresy, które można budować z pojedynczego wierzchołka poprzez dodawanie wierzchołków jeden po drugim, przy czym sąsiedzi każdego nowego wierzchołka są podzbiorem jednego z zamkniętych sąsiedztw poprzedniego wykresu. Są prawie (ale nie do końca) takie same jak wykresy demontowalne, z tą różnicą, że nowy wierzchołek nie musi przylegać do wierzchołka, którego sąsiedztwo jest kopiowane. Kolejność eliminacji wykresu akordowego jest konstrukcją tego typu, w której każdy nowy wierzchołek wybiera podzbiór kliki sąsiedztwa. Podobnie wykresy dziedziczne odległości mają konstrukcję tego typu, w której sąsiedzi każdego nowego wierzchołka to całe zamknięte sąsiedztwo, otwarte sąsiedztwo lub pojedynczy wierzchołek. Każdy nowy wierzchołek nie może zmienić odległości poprzednich wierzchołków, więc ta sekwencja konstrukcyjna ma właściwość, której szukasz.

Jeśli zdefiniujesz wierzchołek v jako „usuwalny”, jeśli mógłby to być ostatni w tej sekwencji (ma otwarte sąsiedztwo, które jest podzbiorem zamkniętego sąsiedztwa innej osoby), wówczas usunięcie innych wymiennych wierzchołków nie zmieni możliwości usunięcia v : jeśli sąsiedztwo v jest podzbiorem u, i usuwamy u jako sąsiedztwo, które jest podzbiorem w, to v jest nadal usuwalne, ponieważ jego sąsiedztwo jest nadal podzbiorem w. Dlatego sekwencje etapów usuwania, które możemy wykonać, aby cofnąć wykres do zera, tworzą antymatroid, a jedną taką sekwencję można znaleźć w czasie wielomianowym przez chciwy algorytm, który wielokrotnie usuwa usuwalny wierzchołek, gdy tylko może go znaleźć. Odwrócenie wyniku tego algorytmu daje sekwencję konstrukcyjną dla danego wykresu. Wykres kostki daje przykład wykresu, który ma twoją właściwość (wykres mediany), ale nie jest w ten sposób możliwy do zbudowania. Myślę, że mediany wykresów, które można zbudować w ten sposób, to dokładnie wykresy kwadratowe (które obejmują regularne siatki). Wykresy, które mają sekwencję konstrukcyjną tego typu, obejmują również wszystkie wykresy, które mają uniwersalny wierzchołek, takie jak wykresy kołowe , więc (w przeciwieństwie do wykresów akordowych i wykresów dziedzicznych odległości) nie są idealne i nie są zamknięte pod indukcyjnymi wykresami podrzędnymi.

David Eppstein
źródło

właściwość tej klasy grafów, której nie jesteś pewien, przypomina kolejność eliminacji dominacji. Ten artykuł wydaje się mieć związek z pierwotnym pytaniem: epubs.siam.org/doi/abs/10.1137/...

JimN

Myślę, że kolejność eliminacji dominatlonu może być taka sama jak dlsmantlability. Ale powinieneś połączyć ten artykuł w rzeczywistą odpowiedź, ponieważ jego „zachowanie kolejności eliminacji odległości” wydaje się być dokładnie tym, czego wymaga pierwotne pytanie.

David Eppstein,

Odwołanie się do klasy wykresów, które zachowują odległości subgrafów przy zamówieniu

Odpowiedzi: