Résoudre exactement2is en utilisant est

Question

J'ai rencontré le problème suivant:

exact2is= {g a exactement 2 ensembles indépendants}

En supposant que donner un graphique g i peut trouver un ensemble indépendant Comment puis-je vérifier si g dispose exactement de 2 ensembles indépendants.

(Je peux vérifier si un graphique contient un ensemble indépendant dans O (1) et trouve également un ensemble indépendant dans O (1))

Je pensais à trouver un ensemble indépendant (s'il y en a une) de taille K, puis retirez un sommet de l'ensemble et vérifiez si le graphique a toujours un ensemble indépendant de taille K -Après que je vérifie, je retourne le sommet au graphique exactement tel qu'il était.

Le problème Mon compte Vérifiez que si un graphique G contient au moins 2 séries indépendants et non exactement.

Quelqu'un a une idée de savoir comment puis-je vérifier si un graphique dispose exactement de 2 ensembles indépendants (en temps polynôme et étant donné que la recherche et la vérification de la recherche d'un ensemble indépendant est O (1))?

Tous les indices ou idées seront appréciés :) Merci

Answer 1

Tout d'abord, si vous pouvez déterminer si un graphique $ g $ contient un ensemble indépendant de taille $ k $ , vous pouvez également trouver un tel ensemble efficacement. Ceci est connu sous le nom de "réduction de la perception de la décision". Voici l'idée de base. Choisissez un Vertex arbitraire $ V $ et supprimez-le. Si le graphique a toujours un ensemble indépendant de taille $ k $ , alors continue à continuer. Sinon, tous les ensembles indépendants de taille $ k $ contiennent $ v $ . En conséquence, retirez $ V $ et tous ses voisins et trouvez un ensemble indépendant de taille $ k-1 $ dans le graphique restant. De cette manière, vous pouvez récupérer un ensemble indépendant de taille $ k $ .

second, comment vérifier si un graphique contient un graphique au moins deux ensembles de taille indépendante $ k $ , en supposant $ k \ geq 2 $ . Tout d'abord, vous déterminez si INTER contient au moins un. Supposons que cela soit, disons $ i $ . Si $ j $ est tout autre ensemble indépendant, alors $ i \ seminus j $ et $ J \ Setminus i $ est à la fois non vide (depuis $ | i |= | j | $ ). En particulier, si $ x \ in i \ seminus j $ et $ y $ est un autre sommet dans $ i $ , puis même après avoir ajouté le bord $ (x, y) $ , l'ensemble $ J $ constituera un ensemble indépendant.

Ceci conduit à l'algorithme suivant: Pour chaque paire de sommets $ x, y \ in i $ , vérifiez si $ G + (x, y) $ contient un ensemble indépendant de taille $ K $ . Si tel est le cas, cet ensemble indépendant est nécessairement différent de $ i $ . Inversement, si un ensemble indépendant de taille $ k $ différent de $ i $ existe nécessairement Soyez un ensemble indépendant dans $ g + (x, y) $ pour certains $ x, y \ in i $ .

Troisième, comment vérifier si un graphique contient exactement deux ensembles indépendants de taille $ k $ . C'est la même chose que de vérifier si un graphique contient au moins les ensembles indépendants . Je pense qu'à ce stade, il est préférable que vous essayiez de généraliser l'argument ci-dessus de deux à trois séries indépendants. Vous pourriez être coincé, mais vous ne saurez pas avant d'essayer.

Answer 2

Si vous êtes autorisé à trouver A est de taille $ K $ in $ \mathcal o (1) $ , alors ce que vous avez écrit est presque la solution.Il suffit de trouver deux fois qu'il est de taille $ k $ , et après ce chèque pour voir s'il en est un autre.

mais généralement, pour les machines Oracle, vous n'êtes pas autorisé à trouver un (dans cet exemple) se trouve dans $ \ MATHCAL O (1) $ temps, et vousne sont autorisés que de vérifier si on existe dans $ \ mathcal o (1) $

.

.

J'espère que cela vous aidera!