Flashcards sur les bases de la théorie des graphes

Question 1

Qu'est-ce qu'un graphe $G=(V,E)$ ?

Accepted Answer

Un graphe est un couple ordonné $G=(V,E)$ où $V$ est un ensemble de sommets (nœuds) et $E$ est un ensemble d'arêtes, chaque arête reliant deux sommets (dans un graphe non orienté, une arête est une paire non ordonnée $\{u,v\}$).

Question 2

Quelle est la différence entre une marche, un chemin et un cycle ?

Accepted Answer

Une marche peut répéter des sommets/arêtes. Un chemin est une marche sans sommets répétés. Un cycle est un chemin fermé (départ = arrivée) sans sommets répétés, sauf le premier/dernier.

Question 3

Que signifie qu'un graphe est planaire, et quelle est la formule d'Euler pour les graphes planaires connexes ?

Accepted Answer

Planaire signifie qu'il peut être tracé dans le plan sans croisement d'arêtes (sauf aux sommets). Pour un plongement planaire connexe, $$V-E+F=2,$$ où $F$ est le nombre de faces (y compris la face extérieure).

Flashcards sur les bases de la théorie des graphes

Maîtrisez les Maths avec l'IA

Ressources d'Apprentissage

Fiable et Reconnu