Avant de commencer, oui c'est un devoir. Je n'aurais pas posté ici si je n'essayais pas aussi fort que possible pour résoudre celui-ci pour les 14 dernières heures et que je me suis nulle part.
Le problème est le suivant: Je veux vérifier si je peux supprimer un bord à partir d'un graphique non dirigé connecté sans le déconnecter ou non dans O (v) Temps, pas seulement linéaire.
Qu'est-ce que j'ai atteint jusqu'à présent:
Un bord de cycle peut être retiré sans déconnecter le graphique, donc je vérifie simplement si le graphique a un cycle. J'ai deux méthodes pouvant être utilisées, l'une est DFS, puis la vérification si j'ai des bords au dos; l'autre est en comptant vs et es et vérifiant si | e | e | = | V | - 1, si c'est vrai, alors le graphique est un arbre et il n'y a pas de noeud que nous pouvons supprimer sans le déconnecter.
Les deux premières approches résolvent le problème, mais les deux ont besoin de O (| e | + | v |), et le livre dit qu'il y a un moyen plus rapide (c'est probablement une approche gourmande).
Puis-je obtenir des indices, s'il vous plaît?
EDIT: Plus spécifiquement, c'est ma question; Compte tenu d'un graphique connecté g = (v, e), puis-je supprimer du bord e dans e et que le graphique résultant soit toujours connecté?
4 Réponses :
De ce que je lis, DFS sans répétition est considéré comme O (| v |), donc si vous prenez Edge E et que vous laissez les deux sommets qu'il relie soit u et v, si vous exécutez DFS de U, ignorant e , vous pouvez supposer que E n'est pas un pont si V est découvert et étant donné que DFS sans répétition est O (| V |), alors cela serait considéré comme étant considéré O (| v |).
Non, un df complet, même sans répétition, est toujours O (| V | + | e |) Puisque vous devez regarder tous les bords pour vous assurer qu'ils ne vont pas à des nœuds que vous n'avez pas encore visité. Si vous arrêtez la traversée dès que vous trouvez une boucle, cependant, cela ne nécessite que de regarder au plus | V | bords.
Je suppose que j'aurais dû clarifier, il semblait un peu évident qu'une fois que vous trouvez v, vous avez prouvé que E n'est pas un pont et a donc répondu au problème, oublié parfois que vous ne pouvez rien prendre pour acquis dans des preuves: D
Tout parcours récursif du graphique, marquage des nœuds comme ils sont visités et court-circuit pour retourner true si vous rencontrez déjà un nœud qui est déjà marqué fera le tour. Cela prend O (| V |) pour traverser le graphique entier s'il n'y a pas de bord pouvant être supprimé et moins de temps s'il s'arrête tôt pour retourner vrai.
Oui, une traversée rectangée de l'ensemble du graphique nécessite O (| V | + | e |) Temps, mais nous ne traversons que le graphe entier s'il n'y a pas de cycles - dans quel cas | E | = | V | -1 et cela ne prend que O (| v |) temps. S'il y a un cycle, nous le trouverons après la traversée au plus | V | bords (et visiter au plus | V | +1 nœuds), qui prend également O (| v |) temps.
Evidemment, lorsque vous traversez à partir d'un nœud (autre que le premier), vous ne considérez pas le bord que vous aviez utilisé pour accéder au nœud, car cela vous ferait de voir immédiatement un nœud déjà visité.
Pouvez-vous m'expliquer votre raisonnement ici, monsieur? Exécution de la procédure d'exploration récursive sur un graphique connecté prend normalement O (| E | + | V |) parce que j'ai besoin de O (v) pour marquer les nœuds, et O (2 | E |) simplement pour vérifier les bords qui connectent les nœuds. Récursive ou non, cela ne se rapproche pas de O (| v |), alors comment retourner-t-il vrai lors de la lutte contre un nœud visité se résume à O (v)? De plus, si je reviens vrai lors de la lutte contre un visité, je pourrais réellement retourner vrai pendant le suivi arrière d'un lavabo, je pourrais dire que j'ai un cycle pendant que je n'ai toujours pas vraiment vérifié si je le fais ou non.
Wow!! Cela fait maintenant un sens parfait! Merci beaucoup monsieur!
Aha. Je pensais qu'il y aurait une astuce impliquant | e | = | v | -1 mais je suis mort mort après les vacances et je ne l'ai pas vue.
La même chose s'est produite ici Haha, je considérais en fait des DFS et de revenir, mais je n'ai jamais pensé comment cela mènerait à O (| V |) hehe. Merci à tous ceux qui ont essayé de répondre =)
Notez que votre autre solution de comptage des nœuds et des bords peut également fonctionner dans O (| V |) temps si vous vous arrêtez après compter | v | bords...
Vous répertoriez tous les bords E et prenez un avantage et marquez une par une à la fois les deux sommets d'extrémité visités. Si lors de la traversée, nous constatons que les deux sommets ont été visités précédemment par certains bords et nous pouvons supprimer ce bord.
Nous devons prendre des bords au plus | V | Il est temps de voir si cette condition satisfait.
Le pire des cas peut aller comme ça, chaque fois que nous prenons un bord, il visitera au moins nouveau sommet. Alors il y a | v | sommets et nous devons prendre | v | bords pour ce bord particulier à trouver.
Le meilleur cas peut être celui avec | v | / 2 + 1 E
Avez-vous entendu parler de Spanning Arbres? Un graphique connecté avec des bords V-1.
Nous pouvons supprimer certains bords d'un graphique connecté G (comme ceux qui créent du cycle) jusqu'à ce que nous obtenions un arbre connecté. Notez que la question ne vous demande pas de trouver un arbre étendu.
question pose de demander si vous pouvez supprimer un ou plusieurs bords du graphique sans perdre la connectivité. Comptez simplement le nombre de bords et la rupture lorsque le nombre augmente au-delà de V-1 car le graphique a une portée pour éliminer plus de bords et devenir une arborescence. Il peut être fait dans O (v) fois si le graphique est donné dans la liste des adjacents.
Être un peu plus précis dans la déclaration. Demandez-vous "étant donné un graphique connecté g = (v, e), puis-je supprimer un bord particulier e dans e et que le graphique résultant soit toujours connecté?" ou "donné un graphique comme auparavant, TeHre existe-t-il un Edge E dans E à celui pour lequel le graphique résultant n'est plus connecté?"
Question éditée, désolé. Je dois vérifier si je peux supprimer un bord de e et que le graphique connecté est toujours connecté.
Le terme technique est Bridge