Jaka jest prawidłowa definicja drzewa

Jak mówi tytuł, jaka jest poprawna definicja drzewa ? Istnieje kilka artykułów, które mówią o drzewach K i drzewach częściowych K jako alternatywnych definicjach dla wykresów o ograniczonej szerokości i widziałem wiele z pozornie niepoprawnych definicji. Na przykład co najmniej jedno miejsce definiuje drzewa- K w następujący sposób:$k$$k$$k$$k$

Wykres nazywa się drzewem wtedy i tylko wtedy, gdy albo G jest kompletnym wykresem z k wierzchołkami, albo G ma wierzchołek v o stopniu k - 1 taki, że G ∖ v jest drzewem k . Częściowe drzewo k to dowolne podgrupa drzewa k .$k$$G$$k$$G$$v$$k − 1$$G \setminus v$$k$$k$$k$

Zgodnie z tą definicją można utworzyć następujący wykres:

1. Zacznij od krawędzi , 2- drzewka.$(v_1, v_2)$$2$
2. Dla utwórz wierzchołek v i i przyłóż go do v i - 1 i v i - 2 .$i=1\ldots n$$v_i$$v_{i-1}$$v_{i-2}$

Spowoduje to utworzenie paska kwadratów z przekątnymi. Podobnie możemy rozpocząć tworzenie pasma od pierwszego kwadratu w kierunku prostopadłym do paska powyżej. Następnie mielibyśmy pierwszy wiersz i pierwszą kolumnę siatki n × n . Wypełnianie siatki jest łatwe, tworząc wierzchołki i łącząc je z wierzchołkami na górze i na lewo.$n$$n \times n$

Rezultatem końcowym jest wykres zawierający siatkę , która w rzeczywistości ma szerokość n .$n\times n$$n$

Prawidłowa definicja drzew- musi być następująca:$k$

Wykres nazywa się drzewem wtedy i tylko wtedy, gdy albo G jest kompletnym wykresem z k wierzchołkami, lub G ma wierzchołek v o stopniu k - 1, tak że sąsiadująca z v tworzy klika k , a G v jest k- drzewo.$k$$G$$k$$G$$v$$k-1$$v$$k$$G \ v$$k$

Następnie wykres podobny do siatki opisany powyżej nie może zostać utworzony.

Mam rację?

Zasadniczo się z tobą zgadzam, z niewielką modyfikacją:

Wykres $G$ jest drzewem $k$ wtedy i tylko wtedy, gdy albo $G$ jest kompletnym wykresem z wierzchołkami $k+1$ , lub $G$ ma wierzchołek $v$ taki, że (otwarte) sąsiedztwo $v$ tworzy $k$ klik, a $G - v$ jest $k$ -tree.

Innymi słowy, $v$ powinien mieć w definicji stopień $k$ , zamiast $k-1$ .

Ja osobiście wolę definicję oddolną, ale to tylko kwestia gustu:

• Pełny wykres na wierzchołkach $k+1$ jest drzewem $k$ .
• $k$ -tree $G$ z $n+1$ wierzchołki ( $n\ge k+1$ ) jest wykonana z $k$ -Tree $H$ o $n$ wierzchołków dodając wierzchołek sąsiadujący dokładnie $k$ wierzchołki tworzą $k$ -clique w $H$ .
• Żadne inne wykresy nie są drzewami- $k$ .

Ta definicja jest nieco zmodyfikowaną wersją definicji z notatek wykładowych Pinara Heggernesa .