Graphe arête-connexe
- Graphe arête-connexe
-
En théorie des graphes, un graphe k-arête-connexe est un graphe connexe qu'il est possible de déconnecter en supprimant k arêtes et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k arêtes dont la suppression rende le graphe déconnecté, mais la suppression de k-1 arêtes, quels qu'elles soient, le fait demeurer connexe.
Un graphe régulier de degré k est au plus k-arête-connexe et k-sommet-connexe. S'il est effectivement k-arête-connexe et k-sommet-connexe, il est qualifié de graphe optimalement connecté.
Exemples
- Pour tout n, le graphe complet Kn est optimalement connecté. Il est (n-1)-sommet-connexe, (n-1)-arête-connexe et (n-1)-régulier.
- Le graphe biparti complet K(1,n) est 1-arête-connexe pour tout n.
- Le graphe cycle Cn est 2-arête-connexe pour tout n>2.
-
Le Graphe de Gray est 3-régulier, 3-sommet-connexe et 3-arête-connexe : il est optimalement connecté.
-
-
Voir aussi
Théorème de Robbins (en)
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe arête-connexe de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe sommet-connexe — En théorie des graphes, un graphe k sommet connexe (ou graphe k connexe) est un graphe connexe qu il est possible de déconnecter en supprimant k sommets et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k sommets dont la… … Wikipédia en Français
Graphe connexe — Sommaire 1 Définition 2 Propriétés 3 Algorithmes 4 Exemples 5 Voir aussi … Wikipédia en Français
Graphe Planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… … Wikipédia en Français
Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier … Wikipédia en Français
Graphe diamant — Représentation du graphe diamant. Nombre de sommets 4 Nombre d arêtes 5 Distribution des degrés 2 (2 sommets) 3 (2 sommets) Rayon 1 … Wikipédia en Français
Graphe de Nauru — Représentation du graphe de Nauru. Notation F24A Nombre de sommets 24 Nombre d arêtes 36 Distribution des degrés 3 régulier … Wikipédia en Français
Graphe de Coxeter — Représentation du graphe de Coxeter. Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Rayon 4 … Wikipédia en Français
Graphe hexaédrique — Représentation du graphe hexaédrique. Nombre de sommets 8 Nombre d arêtes 12 Distribution des degrés 3 régulier Rayon 3 … Wikipédia en Français
Graphe croix — Représentation du graphe croix. Nombre de sommets 6 Nombre d arêtes 5 Distribution des degrés 1 (4 sommets) 2 (1 sommet) 4 (1 sommet) Rayon 2 … Wikipédia en Français
Graphe griffe — Représentation du graphe griffe. Nombre de sommets 4 Nombre d arêtes 3 Distribution des degrés 1 (3 sommets) 3 (1 sommet) Rayon … Wikipédia en Français
