Jai besoin de construire un graphique dexpansion d-régulier pour un petit d fixe (comme 3 ou 4) de n sommets.
Quoi est la méthode la plus simple pour faire cela dans la pratique? Construire un graphe aléatoire d-régulier, qui sest avéré être a.a.s. un expandeur?
Jai aussi lu sur les constructions de Margulis et les graphes Ramanujan qui sont des expandeurs et une construction utilisant un produit zig-zag. Wikipédia donne un aperçu agréable mais très court: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Mais quelle méthode dois-je choisir en pratique?
Pour moi, ces méthodes me paraissent toutes très compliquées à mettre en œuvre et notamment à comprendre et peut-être assez spécifiques. Nexiste-t-il pas de méthodes plus simples, peut-être basées sur des permutations ou plus, pour générer pratiquement une séquence de graphes expanseurs d-réguliers?
Est-il peut-être plus facile de construire des graphes expanseurs bipartis d-réguliers?
Jai aussi une autre question: quen est-il des familles de mauvais expanseurs d-réguliers? Une telle notion a-t-elle un sens? Peut-on construire une famille de graphes d-réguliers (qui sont bien sûr connectés) aussi mauvais que possible en le sens dun expandeur?
Merci davance.
Commentaires
- Il existe des constructions explicites plus faciles que celles que vous avez listées , mais les graphes aléatoires devraient faire laffaire et avoir de meilleurs paramètres.
- Pouvez-vous peut-être donner des noms ou des références aux constructions? Par de meilleurs paramètres, vous voulez dire une meilleure expansion (arête), je suppose?
- Andr á s a donné lexemple que javais en tête, mais en général, les graphes aléatoires sont (presque toujours) meilleurs que les constructions explicites. Non seulement lexpansion des bords est plus grande, une y une autre propriété similaire utile pour votre algorithme est probablement automatiquement satisfaite par des graphiques aléatoires.
- Ok, pour le degré 3, lexemple dAndr á ou les graphiques aléatoires semble être assez bon pour mon application. Il serait intéressant, notamment en ce qui concerne les graphes aléatoires, de construire une famille de graphes à 3 reg qui ne soit pas un expandeur. Mais cest probablement très difficile ou impossible?
- Prenons une union de $ K_4 $ s. Si vous voulez un graphe connecté, supprimez une arête de chaque $ K_4 $ (formant un graphe connu sous le nom de graphe en diamant) et connectez-les en un cycle.
Réponse
Si vous naimez pas les graphiques avec des boucles automatiques, la famille dextendeurs « la plus simple » est probablement celle-ci, donnant des expandeurs qui sont 3-réguliers.
Commencez par un certain nombre premier $ p $, et construisez des sommets numérotés $ 0 $ à $ p-1 $. Pour chaque sommet $ u \ ne 0 $, connectez $ u $ à $ u-1 $ et $ u + 1 $ , modulo $ p $. Connectez également $ u $ au sommet unique $ v $ tel que $ uv \ equiv 1 \ mod p $.
À titre dexemple, le graphe à 7 sommets de la famille est un 7-cycle avec des sommets numérotés séquentiellement autour du cycle; il y a des boucles automatiques sur $ 6 $, $ 0 $ et $ 1 $; enfin, il y a des accords joignant $ 3 $ et $ 5 $, et $ 2 $ et $ 4 $.
Voir https://mathoverflow.net/questions/124708/an-expander-graph pour plus dinformations et des références. Il existe de nombreux indicateurs plus détaillés en recherchant sur » expandeur « at CSTh eory , Math.SE et MO .
Comme le souligne Yuval Filmus, la construction aléatoire est susceptible de donner de meilleurs résultats en général, mais bien sûr peut ne pas donner un expandeur (en particulier pour les petits graphiques).
Commentaires
- Merci pour la remarque. Javais déjà cherché des expandeurs sur les autres sites mais pas sur MO, il semble vraiment y avoir plus de résultats.
Réponse
Étant donné quun graphe régulier aléatoire est un expanseur whp (suivez la référence donnée dans la documentation du code MATLAB ci-dessous), jai utilisé une fois ce qui suit: