Graphes, index et vocabulaire

Édition du: 29/03/2024

INDEX Graphe Topologie Géométrie Logique Dénombrement Jeux	GRAPHES, ARBRES & RÉSEAUX
	Graphes – Index et vocabulaire		Graphe simple
	Graphes – Introduction	Arbres – Introduction	Graphe planaire
	Nœuds	Croisements	Graphe eulérien
	Nombres de Ramsey		Tournoi

Faites un double-clic pour un retour en haut de page

GRAPHES

Index et vocabulaire

Liste des pages relatives aux graphes, aux arbres et aux réseaux.

Graphe comme la description des échanges sur Internet;

Arbres comme les arbres généalogiques; et

Réseaux comme la disposition des rues de Manhattan.

Puis petit lexique des graphes.

Sommaire de cette page

>>> Rubriques – Graphes, arbres & réseaux

>>> Index graphes

>>> Vocabulaire des graphes

Débutants

Dénombrement

Glossaire

Combinatoire

Anglais : Graph

Rubriques – GRAPHES, ARBRES & RÉSEAUX

Anglais: Graphs, trees and lattice paths

Introduction – Généralités	Graphes – Introduction	Arbres – Introduction	Graphes – Vocabulaire
Introduction – Généralités	Nœuds	Croisements	Nombre chromatique
Graphes – Types	Graphe simple	Graphe eulérien	Graphe planaire
	Graphe simple S5	Graphe de Delaunay	Multiple et diviseurs
	Tournoi
Graphes – Applications	Chemin le plus court	Voyageur de commerce	Ivrogne
	Pont de Königsberg	Cinq pays	Trois maisons
	Petit monde	Cheval	Colonies de fourmis
Arbres	Arbres – Introduction	Arbres simples	Arbres de distribution
	Arbres étiquetés	Arbres – Catalan
	Arbre couvrant	Arbre de Steiner
Réseaux Grilles	Chemin sur réseau	Chemin le plus court	Chemin auto-évitant
	Périple du cavalier	Périple de la tour	Diagramme de Voronoï
	Taxi dans Manhattan
Suites de nombres associés	Suites pour dénombrer	Nombres de Catalan	Nombres de Delannoy
	Nombres Manhattan	Nombres de Narayana	Nombres de Dyck
	Nombres octaédriques	Nombres de Motzkin	Nombres de Ramsey
Nombres de Catalan	Définition	Pascal	Parenthèses
	Valeurs	Hipparque	Escaliers
	Fuss-Catalan	Chemins de Dyck	Arbres – Catalan

INDEX Graphes

Graphes – Introduction et types

Arbres – Introduction et types

Vocabulaire des graphes

Arbre de distribution

Arbres – Catalan

Arbres étiquetés

Arbres simples

Binaire (arbre -)

Biparti (graphe - )

Catalan – Nombres

Cayley (nombre et arbre)

Chemin de la fourmi - Pavé, cylindre …

Chemin le plus court

Chemins auto-évitant

Chemins de Dyck

Chemins eulérien

Chemins sur grille

Cinq pays

Colonies de fourmis

Coloration

Complet( arbre -)

Complet( graphe -)

Construction de Henneberg

Couvrant (arbre -)

Croisements – Graphes

Delannoy (nombres de -)

Diagramme de Voronoï

Dominos et graphe

Dualité

Dyck (chemins de -)

Échiquier et graphe

Énigmes et paradoxes

Enraciné (arbre)

Escaliers

Escaliers – Catalan

Étiqueté (arbre -)

Étiqueté (graphe -)

Euler (formule -)

Eulérien (graphe -)

Graphe de Delaunay

Graphe de Moser

Graphe et organisation de tournois

Graphe planaire

Graphes et problèmes NP

Graphes simples à cinq sommets

Intelligence artificielle

Isomorphe

Ivrogne

K3, 3

Königsberg (ponts de -)

Le parcours du cavalier

Logique formelle

Manhattan (nombres)

Monstre (groupe -)

Motzkin (nombres de -)

Multiple et diviseurs

Narayana (nombres de -)

Nœuds

Nombre chromatique

Parenthèses

Périple du cavalier

Petit monde

Planaire (graphe - )

Polygones flexibles ou rigidifiés

Quatre couleurs – (Problème -)

Raisonnement

Ramsey – Nombres et théorie

Relation d'Euler

Relier les points d'un coup de crayon

Réseau et nombres de Manhattan

Réseaux – Grille – Treillis

Rigide – Polygone rigide (braced polygon)

Rubik's cube

Simple (arbre - )

Simple (graphe - )

Sudoku

Théorème de Laman

Topologie – Index

Tour de Brahmâ

Trajets

Trois maisons

Voyageur de commerce

INDEX VOISINS: Arbre / Graphe / Topologie / Dénombrement / Logique / Géométrie / Jeux et énigmes

Vocabulaire des graphes		haut
*Sommets ou nœuds*	Ce genre de graphe est dit réseaux de points (sommets).
*Distance entre deux sommets*	Longueur de la plus courte chaine qui relie ces deux sommets.
*Ordre du graphe*	Quantité de sommets dans ce graphe.
*Diamètre du graphe*	La plus grande des distances entre les paires de sommets du graphe.
*Rayon du graphe*	La plus petite des distances entre les paires de sommets du graphe.
*Degré d'un sommet*	Quantité d'arêtes présentes à ce sommet. >>>
*Arêtes ou arcs*	Segment linéaire ou courbe joignant les sommets. Arc est plutôt utilisé lorsque l'arête est orientée.
*Adjacent (sommets)*	Deux sommets sont adjacents s'ils sont reliés par une arête.
*Face d'un graphe*	Chacune des régions délimitées par les arêtes, y compris la région extérieure. Région délimitée par un chemin passant par trois sommets et ne contenant aucun autre sommet.
*Graphe connexe*	Graphe tels que toute paire de sommet peut être reliée par une chaine (une suite d'arêtes). Ce graphe possède au moins n – 1 arêtes.
*Clique*	Sous-ensemble des sommets d'un graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents.
*Diagramme sagittal*	Graphe qui représente les relations entre deux ensembles finis. Il permet notamment de visualiser si une application est injective, surjective ou bijective.
*Arbre*	Graphe qui ne contient aucun cycle (boucle). Ils sont donc planaires
*Graphe complet*	Tous les sommets sont adjacents. Alors, chaque sommet est relié à tous les autres.
*Graphe de Grinder*	*Voir exemples* >>>
*Graphe k-facteur*	Chaque sommet ne reçoit que k arêtes.
K5	Graphe complet à 5 sommets. Il n'est pas planaire.
*Graphe biparti ou cyclique*	Les sommets sont divisés en deux groupes. Les sommets de l'un sont reliés aux sommets de l'autre. Voir Nombre de croisements des graphes bipartis.
*K3,3*	Graphe complet biparti de 3 + 3 sommets. Il n'est pas planaire
*Graphe planaire*	Un graphe planaire est dessiné sur une feuille de papier, dans un plan, sans que les arêtes se croisent.
*Nombre chromatique*	Quantité maximale de couleurs pour colorier un graphe. >>>
*Graphe planaire topologique*	Le graphe est dessiné dans une version qui montre que les arêtes ne se croisent pas. Cette version du graphe est aussi appelée la carte du graphe planaire.
*Graphe planaire connexe*	Graphe qui n'a pas de sommets ou de sous-graphes isolés. Il existe toujours un chemin pour relier deux sommets.
*Chemin eulérien* *Chaine eulérienne*	Le tracé en un seul trait est appelé chemin eulérien. La chaine contient toutes les arêtes et chaque arête n'est décrite qu'une seule fois.
*Cycle eulérien*	Chaine eulérienne fermée: le sommet de départ et celui d'arrivée sont les mêmes.
*Graphe eulérien*	Graphe que l'on peut dessiner sans jamais lever le crayon et sans passer deux fois par la même arête. Un graphe est eulérien si et seulement si il contient une chaine eulérienne ou un cycle eulérien.
*Chemin hamiltonien*	Un tracé qui passe par tous les sommets (sans forcément parcourir toutes les arêtes du graphe). Un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une fois et une seule. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Exemples avec le problème de la table ronde de Dudeney.
*Graphes isomorphes*	Graphes de mêmes caractéristiques: le degré des sommets est conservé. La longueur des arcs et leur courbure n'influent pas sur les caractéristiques du graphe. Exemple Leur résolution en temps polynomial est un problème ouvert. Voir Graphes isomorphes

Suite en Caractérisation des graphes

Haut de page

Retour	Graphe planaire
Suite	Arbres à dénombrement avec nombres de Catalan Arbres de distribution Chemin le plus court Vocabulaire des graphes Coloration des graphes (nombre chromatique) Graphes et problèmes NP Petit monde Sept amis autour d'une table
Voir	Code Gray Croissance logistique Énigmes et paradoxes Graphe de Delaunay Intelligence artificielle Jeux – Index Logique formelle Percolation Relier les points d'un seul coup de crayon Topologie – Glossaire Tour de Brahmâ Trois maisons (énigme des -)
Sites	Théorie des graphes – Michel Rigo – pdf 176 pages Types of Graphs with Examples – Geeksforgeeks *OEIS A006125 – a(n) = 2^(n(n-1)/2) OEIS A001187 – Number of connected labeled graphs with n nodes**
Cette page	http://villemin.gerard.free.fr/aMaths/Topologi/aaaGraph/GrapheIX.htm