J'utilisais Jung ( http://jung.sourceforge.net/ ) pour visualiser le classement des pages et je l'ai trouvé un peu lent et difficile à mettre à l'échelle au-delà de 100 nœuds. Je me demandais quels autres outils les gens utilisent pour l'analyse et la visualisation des réseaux / réseaux...
Ci-dessous, MSO désigne la logique monadique du second ordre des graphiques avec des quantifications de sommets et de contours. Soit une petite famille fermée de graphes. Il découle de la théorie de graphe mineur de Robertson et Seymour que F est caractérisée par une liste finie H 1 , H 2 , . . . ,...
Je m'intéresse aux modèles de graphes aléatoires similaires aux graphes de vrais réseaux informatiques. Je ne sais pas si le modèle commun bien étudié ( n sommets, chaque bord possible est sélectionné avec la probabilité p ) est bon pour étudier les réseaux informatiques réels...
Je cherche des moyens de maintenir un arbre couvrant relativement équilibré d'un graphique, alors que j'ajoute de nouveaux nœuds / arêtes au graphique. J'ai un graphique non orienté qui commence comme un seul nœud, la "racine". À chaque étape, j'ajoute au graphique soit un nouveau nœud et un bord...
On vous donne un graphe avec n sommets. Il peut être bipartite si vous le souhaitez. Il existe m ensembles d'arêtes E 1 , … , E m ⊆ E (disons disjoints). Je m'intéresse au problème de trouver un sous-ensemble S ⊆ V , aussi petit que possible (ou même plus petit), tel que le graphe induit G S ait au...
Supposons que nous ayons un graphique pondéré non orienté (avec des poids non négatifs). Supposons que tous les chemins les plus courts dans G soient uniques. Supposons que nous ayons ces chemins (séquences d'arêtes non pondérées), mais ne connaissons pas lui-même. Pouvons-nous produire un qui...
Soit le nombre d'arbres couvrant un graphe à sommets. Il existe un algorithme qui calcule dans les opérations arithmétiques . Cet algorithme consiste à calculer , où Q est le laplacien de G et J est la matrice constituée uniquement de 1 . Pour plus d'informations sur cet algorithme, voir Biggs -...
Soit un simple graphe sur sommets sans sommet de degré . Supposons que pour deux sommets de , il existe un sommet unique adjacent à chacun d'eux. Il s'agit d'un exercice de A Course in Combinatorics , van Lint et Wilson, pour prouver qu'un tel graphique est régulier.ggGnnn( n > 3 )(n>3)(n >...
Soit un graphe non orienté non pondéré avec sommets et arêtes. Est-il possible de prétraiter et de produire une structure de données de taille afin qu'il puisse répondre aux requêtes de la forme "distance entre et " dans le temps O (n)?n m G m ⋅ p o l y l o g ( n ) u vgGGnnnmmmgGGm ⋅ p o l y l o g...
Existe-t-il un exemple d'une classe de graphes pour laquelle le problème de coloration des sommets est en P mais l'ensemble indépendant est le problème est NP
Feedback Vertex Set est NP-complete pour les graphiques généraux. Il est connu qu'il est NP-complet pour les graphiques bornés de degré 8 en raison d'une réduction de la couverture des sommets. L' article de Wikipédia indique qu'il est résoluble en temps poly pour les graphiques bornés de degré 3...
Quelqu'un connaît-il un résultat de complétude NP pour le problème DOMINATING SET dans les graphiques, limité à la classe des graphiques bipartites planaires de degré 3 maximum? Je sais qu'il est NP-complet pour la classe des graphes planaires de degré maximum 3 (voir le livre Garey et Johnson),...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
De nombreux problèmes de graphes durs peuvent être résolus en temps polynomial sur des graphes de largeur d'arbre bornée . En effet, les manuels utilisent généralement, par exemple, l'ensemble indépendant comme exemple, ce qui est un problème local . En gros, un problème local est un problème dont...
Existe-t-il une séquence de graphes non dirigés , où chaque a exactement sommets et le problème{ Cn}n ∈ N{Cn}n∈N\{C_n\}_{n\in \mathbb N}CnCnC_nnnn Étant donné et un graphe , est-il un sous-graphe induit de ?G C n GnnnggGCnCnC_nggG est connu pour être dans la classe ? (Par exemple, lorsque , c'est...
Comment puis-je déterminer le nombre de chemins simples uniques dans un graphique non orienté? Soit pour une certaine longueur, soit pour une plage de longueurs acceptables. Rappelez-vous qu'un chemin simple est un chemin sans cycle, je parle donc de compter le nombre de chemins sans...
Je m'intéresse au problème suivant: étant donné une matrice , y a-t-il un graphe non orienté sur n sommets dont la matrice d'adjacence au carré est cette matrice?n × nn×nn\times nnnn La complexité de calcul de ce problème est-elle connue? Remarques: Bien sûr, cela peut aussi être formulé comme un...
Que sait-on de la complexité exacte du problème de chaîne la plus courte? Peut-il être résolu plus rapidement que ? Existe-t-il des algorithmes connus qui résolvent la super chaîne la plus courte sans réduire au TSP?O∗(2n)O∗(2n)O^*(2^n) UPD: supprime les facteurs polynomiaux.O∗(⋅)O∗(⋅)O^*(\cdot) Le...
La classe de graphique suivante est-elle connue dans la littérature? La classe de graphes est paramétrée par des entiers positifs et et contient chaque graphe telle sorte que pour chaque sommet , le sous-graphe de induit sur tous les sommets à distance au plus partir de dans a une largeur d'arbre...
La dynamique de Glauber est une chaîne de Markov sur les colorations d'un graphe dans laquelle à chaque étape on tente de recolorer un sommet choisi au hasard avec une couleur aléatoire. Il ne se mélange pas pour les 3 couleurs d'un cycle de 5: il y a 30 3 couleurs, mais seulement 15 d'entre elles...