Théorie des graphes, Réseau hexagonal et matrice d'adjacence

[Mathusalem]

Bonjour,

Dans un problème de recherche je suis confronté à l''étude d'une sorte de réseau. Le réseau a la propriété que ses noeuds sont pour leur grande majorité connectés seulement à 3 autres noeuds. Au départ, je considère que les connections ont le même poids.

On définit la matrice d'adjacence en numérotant les noeuds de i=1 à n, avec n le nombre de noeuds dans le réseau. La matrice A_ij = 1 si les noeuds i et j sont connectés, 0 sinon.

Je me demande quelle est la topologie de mon réseau, car en fonction de cela, je peux appliquer certains résultats dessus. J'ai commencé à dessiner des noeuds connectés à 3 autres noeuds etc... et j'ai instinctivement commencé à dessiner un réseau hexagonal. Si c'était le cas, ça me permetrait de dégager des résultats analytiques du problème.

Ma question: Un réseau hexagonal fini possède la propriéte que la grande majorité de ses noeuds (i.e les noeuds qui ne sont pas sur le pourtour du réseau) sont connectés à 3 autres noeuds. En partant de l'inverse, sachant que j'ai un réseau dont la grande majorité des noeuds est reliée à 3 autres noeuds (sachant que ce n'est pas une condition suffisante) comment puis-je déterminer si mon réseau possède la topologie d'un réseau hexagonal ? Est-ce que la matrice d'adjacence / laplacien, etc... du graphe peut encoder cette topologie (p.ex dans son spectre?). J'ai de la peine à trouver des résultats là-dessus dans la littérature mathématique.

Merci d'avance,
Math

[Ben314]

Salut,
A mon avis, de savoir que (presque) tout les sommets sont de degré 3, c'est très très loin d'être suffisant pour caractériser un "graphe hexagonal", quelque soit la définition que l'on donne à cette expression.
Il me semble qu'au grand minimum, il faudrait par exemple demander à ce qu'il n'existe pas de cycles de longueur <6 et qu'à contrario, il existe "beaucoup" de 6-cycle (mais là, ça commence à dépendre de la définition qu'on va prendre de "graphe hexagonal" : si on accepte n'importe quoi qui soit un sous graphe d'un graphe "purement hexagonal", il peut très bien n'y avoir aucun 6-cycles, mais dans ce cas, il y aura pas mal de sommets de degrés <3).
Après, si on est draconien sur la définition de "graphe hexagonal" en demandant qu'un tel graphe soit constitué de mailles hexagonales sans aucune arrête manquante (ce que j'appelle "purement hexagonal" ci dessus) , ça doit être très facile à repérer vu que, partant de n'importe quel sommet, tu doit trouver un 6-cycle puis que dés que ce 6 cycle est trouvé, tout le reste de la structure du graphe doit suivre une logique parfaitement définie donc il suffit de vérifier que "ça colle".

[Robot]

Remarque : on peut éliminer tous les sommets de valence d > 3 dans un graphe en "épaississant" de tels sommets en des polygones à d sommets.