Séance de cours

Comptage des arbres étiquetés

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre le comptage des arbres étiquetés en utilisant les codes Prüfer, fournissant une formule et une preuve faciles. Il explique un algorithme pour convertir les arbres en séquences et vice versa, connu sous le nom d'Algorithm 2. La séance de cours démontre l'application de l'algorithme 1 et de l'algorithme 2, montrant comment ils fournissent des cartes entre les arbres et les séquences. La preuve des théorèmes se fait par induction, en commençant par le cas de base de n=2. La séance de cours se termine par des exercices sur la détermination du code Prüfer d'un arbre et l'apparence des sommets dans le code.

Source officielle

Concepts associés (32)

Arbre binaire

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.

Vertex cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.

Sommet (théorie des graphes)

vignette|Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe. Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins. alt=A small example network with 8 vertices and 10 edges.|vignette|Réseau de huit sommets (dont un isolé) et 10 arêtes.

Degré (théorie des graphes)

thumb|Un graphe non orienté où on a indiqué le degré de chaque sommet sur ce sommet. Dans ce graphe, le degré maximal est et le degré minimal est . En mathématiques, et plus particulièrement en théorie des graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois. Le degré d'un sommet est noté . Dans le cas d'un graphe orienté, on parle aussi du degré entrant d'un sommet , c'est-à-dire le nombre d'arcs dirigés vers le sommet , et du degré sortant de ce sommet , c'est-à-dire le nombre d'arcs sortant de .

Codage de Prüfer

En mathématiques, le codage de Prüfer est une méthode pour décrire de façon compacte un arbre dont les sommets sont numérotés. Ce codage représente un arbre de n sommets numérotés avec une suite de n-2 termes. Une suite P donnée correspond à un et un seul arbre numéroté de 1 à n. Les suites de Prüfer ont été utilisées pour la première fois par Heinz Prüfer pour démontrer la formule de Cayley en 1918. On peut aussi les utiliser en programmation informatique pour enregistrer la structure d'un arbre de façon plus compacte qu'avec des pointeurs.

Afficher plus

Séances de cours associées (64)

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Modèles graphiques : Représentation des distributions probabilistes

Couvre les modèles graphiques pour les distributions probabilistes à l'aide de graphiques, de nœuds et de bords.

Complexité et induction: Algorithmes et preuves

Explore la complexité du pire cas, l'induction mathématique, et des algorithmes comme la recherche binaire et le tri d'insertion.

Relations de récurrence linéaire

Explore les relations de récurrence linéaires, y compris des exemples comme les nombres de Fibonacci et la preuve de théorèmes liés.

Analyse réelle : Séquences et limites

Couvre les séquences réelles, l'induction, les limites et la convergence dans l'analyse mathématique.

Afficher plus

Concepts associés (32)

Arbre binaire

Vertex cover

Sommet (théorie des graphes)

Degré (théorie des graphes)

Codage de Prüfer

Afficher plus