Bonjour.
Quelqu'un a t-il des liens sur les propriétés des 2-graphes (j'ai cherché sur google sans succès).
Pour info, un 2-graphe est un triplet (u,G,v) avec G un graphe et u et v deux sommets distincts de G.
Merci.
Version imprimable
Bonjour.
Quelqu'un a t-il des liens sur les propriétés des 2-graphes (j'ai cherché sur google sans succès).
Pour info, un 2-graphe est un triplet (u,G,v) avec G un graphe et u et v deux sommets distincts de G.
Merci.
je ne comprend pas ta notation ... en général un n-graphe est un graphe de multiplicité n ie il y a au plus n arêtes ou arcs entre deux sommets
Pas forcément, suivant les auteurs (c'est toujours un problème dans les graphes), un n-graphe est un graphe d'ordre n, donc uniquement une notion sur un noeud (qui a au maximum n arêtes/arcs). Cette définition n'est pas équivalente à la tienne.Citation:
en général un n-graphe est un graphe de multiplicité n ie il y a au plus n arêtes ou arcs entre deux sommets
Tu peux toujours prendre les propriétés d'un graphe d'ordre n et les écrire avec un graphe d'ordre 2.Citation:
Quelqu'un a t-il des liens sur les propriétés des 2-graphes (j'ai cherché sur google sans succès).
Que cherches-tu en particulier ?
Je cherche à prouver que tout 2-graphe série parallèle possède un nombre d'arêtes inférieur ou égal à 2 fois le nombre de sommets (j'ai essayé sans succès par récurrence sur le nombre de sommets).Citation:
Envoyé par PRomu@ld
Je cherche ensuite à prouver que tout 2-graphe série parallèle est 3-coloriable.
et tu penses qu'un graphe ayant au plus deux sommets est intéressant à étudier ? lol ..., Yaris peut tu nous en donner un exemple de 2-graphe ...Citation:
Envoyé par PRomu@ld
je me suis planté entre ordre et degré (pas réveillé :oops:)Citation:
et tu penses qu'un graphe ayant au plus deux sommets est intéressant à étudier ?
Prends le graphe suivant :
Si tu prends ta définition, c'est un 2-graphe (pas plus de deux arêtes entre deux sommets), avec celle que j'ai cité (en prenant bien en compte le degré et pas l'ordre ;)) , c'est un 4-graphe.Citation:
A -- B
A -- A
A -- C
Je suis preneur aussi.Citation:
peut tu nous en donner un exemple de 2-graphe ...
non ça c est un graphe simple avec une boucle , un graphe a degré de multiplicité est par exemple
Citation:
a---b
a---b
a--c
b--c
Non, ça n'est pas un graphe simple puisqu'il y a une boucle. On peut trouver quelques fois le terme de graphe bouclé mais ça ne repose pas sur des définitions précises.Citation:
non ça c est un graphe simple avec une boucle
En fait, le problème que je voulais soulever c'est qu'un 2-graphe peut être interpréter de façons différentes suivants l'enseignement/culture que l'on a reçu des graphes. Pour certains, c'est la première forme d'un multiplet/hypergraphe (donc autorisant au plus deux arêtes (u,v)), pour d'autres c'est un graphe de degré 2 (donc avec au plus deux arcs/arêtes par sommets), ce qui n'est pas la même chose.
L'exemple que j'ai cité (comme le tiens d'ailleurs) représente un cas où suivant l'interprétation que l'on en a, le graphe n'appartient pas à une des deux catégories.
en tout les cas j utilise la notation de LeBerge ... eh oui je me suis trompé en rajoutant simple ... car par définition un graphe simple est sans boucle de degré de multiplicité 1