Comment savoir si un avantage est sur une voie

Question

Étant donné un graphe non orienté G = V, E, 2 sommets: x, y et e de bord,

Je voudrais vérifier s'il y a un chemin de x à y qui contient le bord donné e. Ce que j'ai pensé: Résolvez ceci en définissant un flux réseau où x et y sont source et sink et vérifiez si le flux dans e est supérieur à 0 cela signifie qu'il y a un chemin. mais il y a deux problèmes:

1. Je ne sais pas comment diriger vers les bords
2. Quelle serait la capacité de chaque bord?

Donc je suppose que ce n'est pas la bonne approche ... Si quelqu'un peut donner une idée ce serait génial.

Answer 1

Une approche pourrait être la suivante:

1. Annuler le bord e = (u, v) à partir de E (G).
2. Si un chemin xy contient e alors le chemin sera l'une des deux formes suivantes: (1) x * -> u -> v * -> y ou (2) x * -> v -> u * -> y où * -> signifie accessible. Utilisez ce fait pour vérifier si l'un des cas suivants est vrai 2.1. x est accessible depuis u et y est joignable depuis v. 2.2. x est accessible depuis v et y est accessible depuis u. Nous pouvons utiliser BFS pour trouver reachablility.