Quelle est la définition correcte de

Comme le titre l'indique, quelle est la définition correcte de arbre? Il existe plusieurs articles qui parlent d' arbres et d' arbres partiels comme définitions alternatives pour les graphiques avec une largeur d'arbre bornée, et j'ai vu de nombreuses définitions apparemment incorrectes. Par exemple, au moins un endroit définit les arbres comme suit:k k $k$$k$$k$$k$

Un graphe est appelé arbre si et seulement si est le graphe complet avec sommets, ou si a un sommet de degré tel que est un arbre. Un arbre partiel est un sous-graphe d'un arbre .$k$$G$G v k - $k$$G$$v$$k − 1$k k $G \setminus v$$k$$k$$k$

Selon cette définition, on peut créer le graphique suivant:

1. Commencez par un bord , un 2- arbre.$(v_1, v_2)$$2$
2. Pour , créez un sommet v i et rendez-le adjacent à v i - 1 et v i - 2 .$i=1\ldots n$$v_i$$v_{i-1}$$v_{i-2}$

Cela créerait une bande de carrés avec des diagonales. De même, nous pouvons commencer à créer une bande à partir du premier carré dans une direction orthogonale à la bande ci-dessus. Ensuite, nous aurions la première ligne et la première colonne d'une grille n × n . Il est facile de remplir la grille en créant des sommets et en les joignant aux sommets à son dessus et à sa gauche.$n$$n \times n$

Le résultat final est un graphique qui contient une grille , qui, en effet, est connue pour avoir une largeur d'arbre n .$n\times n$$n$

Une définition correcte des arbres doit être la suivante:$k$

Un graphe est appelé arbre si et seulement si G est un graphe complet avec k sommets, ou G a un sommet v de degré k - 1 tel que le voisin de v forme une k -clique, et G v est un k- arbre.$k$$G$$k$$G$$v$$k-1$$v$$k$$G \ v$$k$

Ensuite, le graphique de type grille décrit comme ci-dessus ne peut pas être créé.

Ai-je raison?

Je suis essentiellement d'accord avec vous, avec juste une petite modification:

Un graphe $G$ est un arbre $k$ si et seulement si $G$ est un graphe complet avec $k+1$ sommets, ou $G$ a un sommet $v$ tel que le voisinage (ouvert) de $v$ forme une $k$ -clique, et $G - v$ est un $k$ arbre.

En d'autres termes, $v$ devrait avoir le degré $k$ , au lieu de $k-1$ dans votre définition.

Personnellement, je préfère la définition ascendante, mais ce n'est qu'une question de goût:

• Le graphe complet sur $k+1$ sommets est un $k$ arbre.
• A $k$ -tree $G$ avec $n+1$ sommets ( $n\ge k+1$ ) peut être construit à partir d' une $k$ -tree $H$ avec $n$ sommets par l' ajout d' un sommet adjacent à exactement $k$ sommets qui forment un $k$ -clique en $H$ .
• Aucun autre graphique n'est $k$ arbres.

Cette définition est une version légèrement modifiée de la définition des notes de cours de Pinar Heggernes .