Discussion :

[yaris20]

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.

[benDelphic]

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

[PRomu@ld]

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.

Quelqu'un a t-il des liens sur les propriétés des 2-graphes (j'ai cherché sur google sans succès).

Tu peux toujours prendre les propriétés d'un graphe d'ordre n et les écrire avec un graphe d'ordre 2.

Que cherches-tu en particulier ?

[yaris20]

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).
Je cherche ensuite à prouver que tout 2-graphe série parallèle est 3-coloriable.

[benDelphic]

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.



Tu peux toujours prendre les propriétés d'un graphe d'ordre n et les écrire avec un graphe d'ordre 2.
?

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 ...

[PRomu@ld]

et tu penses qu'un graphe ayant au plus deux sommets est intéressant à étudier ?

je me suis planté entre ordre et degré (pas réveillé )

Prends le graphe suivant :

A -- B
A -- A
A -- C

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.

peut tu nous en donner un exemple de 2-graphe ...

Je suis preneur aussi.

[benDelphic]

non ça c est un graphe simple avec une boucle , un graphe a degré de multiplicité est par exemple

a---b
a---b
a--c
b--c

[PRomu@ld]

non ça c est un graphe simple avec une boucle

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.

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.

[benDelphic]

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