J'ai un graphique qui se compose uniquement de graphiques en étoile. Un graphique en étoile se compose d'un nœud central ayant des arêtes à tous les autres nœuds. Laissez H 1 , H 2 , ... , H n être différents graphiques étoiles de différentes tailles qui sont présents dans G . Nous appelons...
Lors de l'introduction de la décomposition modulaire des graphes , la plupart des auteurs utilisent le graphe à 11 sommets, que je copie de wikipedia. La question est de savoir qui en est le concepteur d'origine. (Je ne demande pas qui a dessiné ce graphique pour wikipedia, mais la source originale...
L'un des principaux problèmes de l'énumération des graphes est de déterminer la «forme» d'un graphe, par exemple la classe d'isomorphisme d'un graphe particulier. Je suis pleinement conscient que chaque graphique peut être représenté comme une matrice symétrique. Cependant, pour obtenir sa forme,...
Définissez un maillage en 3D comme une collection connectée de tétraèdres aux intérieurs disjoints (donc les tétraèdres ne partagent que k-faces, ). Étant donné un graphe arbitraire, existe-t-il une procédure efficace pour tester s'il peut être incorporé en tant que maillage?k ≤ 2k≤2k \le 2 Ici,...
Je voudrais avoir une limite sur la cardinalité de l'ensemble des graphes d'unité de disque avec sommets. Il est connu que vérifier si un graphe est membre de cet ensemble est NP-difficile. Cela conduit-il à une borne inférieure de la cardinalité, en supposant P NP?NNN≠≠\neq Par exemple, supposons...
Je voulais savoir quelles sont les applications de SGT dans le domaine de la théorie de l'information et du codage et peut-être des communications. Le plus lié qui me vient à l'esprit est le travail sur les codes d'extension Michael Sipser et Daniel Spielman, "Expander Codes", IEEE Transactions on...
Ma question est un peu vague. Je me demandais si (et comment), nous pouvons appliquer la notion de largeur d'arbre aux problèmes d'emballage dans les graphiques. Je serais heureux de tout aperçu ou référence de travaux de recherche antérieurs à ce sujet (en supposant qu'il s'agit d'une relation)....
Existe-t-il des résultats connus sur la complexité de trouver un séparateur (de toute taille) satisfaisant une propriété donnée? Je sais qu'un séparateur clique est facile à trouver (temps polynomial) et je sais aussi que de nombreux articles considèrent le problème de trouver de petits séparateurs...
Dans une question précédente, Algorithme paramétré pour trouver des bicliques , je me suis demandé s'il y avait des algorithmes paramétrés rapides pour trouver un -biclique dans un graphe de sommets n et j'ai appris qu'il était ouvert s'il était FPT par rapport à k . Est-ce la même chose pour le...
Supposons que nous ayons un graphe sur nnn nœuds. Nous aimerions attribuer à chaque nœud soit un +1+1+1 soit un −1−1−1 . Appelons cela une configuration σ∈{+1,−1}nσ∈{+1,−1}n\sigma \in \{+1,−1\}^n . Le nombre de +1+1+1 s que nous devons attribuer est exactement sss (d'où le nombre de −1−1−1 s est...
kkk points distincts sont choisis au hasard dans une grille . (Évidemment et est un nombre constant donné.) Un graphique pondéré complet est construit à partir de ces points de telle sorte que le poids de l'arête entre le sommet et le sommet est égal à la distance Manhattan de deux sommets sur la...
J'ai rencontré ce problème d'appariement pour lequel je ne suis pas en mesure d'écrire un algorithme de temps polynomial. Soit graphiques pondérés complets avec les ensembles de sommets et , respectivement, où . Soit également et les fonctions de pondération sur les bords de et , respectivement.P V...
Considérons un graphique avec tous les bords ayant une capacité unitaire. On peut trouver la coupure min en temps polynomial. Supposons que je suis autorisé à augmenter la capacité de n'importe quel bords à l'infini (équivalent à la fusion des nœuds de chaque côté du bord). Quelle est la façon...
J'essaie de trouver un graphique avec ces propriétés pour mes études, mais malheureusement je ne trouve pas un tel graphique. Est-ce que quelqu'un sait s'il y a ce graphique, ou pourquoi est-il impossible
Je résous un problème de "mélange" d'ensembles d'images qui se chevauchent. Ces ensembles peuvent être représentés par un graphique pondéré non orienté tel que celui-ci: Chaque nœud représente une image. Les images qui se chevauchent sont reliées par un bord. Le poids des bords représente la taille...
Combien de cycles ( k ≥ 3 ) y a-t-il dans un graphe à n sommets tel que le graphe n'a pas de cycle C m ( m > k ) .CkCkC_k (k≥3)(k≥3)(k \geq 3)nnn CmCmC_m (m>k)(m>k)(m>k) Par exemple , k = 3 , alors le graphique aura au plus deux C 3 de sorte que G n'aura pas de C k ( k > 3 )...
Supposons que j'ai des ensembles avec des éléments pris parmi les r possibles. Chaque ensemble est de taille n ( n < r ), où les ensembles peuvent se chevaucher. Je veux déterminer si les deux problèmes suivants sont NP-complets ou non:PPPrrrnnnn <
La vérification de la transitivité d'un digraphe n'est-elle pas plus facile que (en termes de complexité asymptotique) de prendre la fermeture transitive du digraphe? Connaissons-nous mieux une borne inférieure que pour déterminer si un digraphe est transitif ou non?Ω (
Il y a eu quelques questions ( 1 , 2 , 3 ) sur l'achèvement transitif ici qui m'ont fait penser si quelque chose comme ça était possible: Supposons que nous obtenions un graphe orienté en entrée et que nous souhaitions répondre aux requêtes de type " ?", C'est-à-dire demander s'il existe une arête...
Je cherche des références pour le problème suivant: étant donné les entiers et , énumérer tous les graphes planaires non isomorphes sur sommets et la largeur d'arbre . Je m'intéresse à la fois aux résultats théoriques et pratiques, mais surtout aux algorithmes pratiques qu'il est possible de coder...