Je lis sur le problème de débit maximum ici . Je ne pouvais pas comprendre l'intuition derrière le graphique résiduel. Pourquoi considérons-nous les bords arrière lors du calcul du débit? Quelqu'un peut-il m'aider à comprendre le concept de graphique résiduel? Comment l'algorithme change-t-il dans...
Si un graphe est connecté et n'a pas de chemin d'une longueur supérieure à , prouver que tous les deux chemins en de longueur ont au moins un sommet en commun. k G kgGGkkkgGGkkk Je pense que ce sommet commun devrait être au milieu des deux chemins. Parce que si ce n'est pas le cas, nous pouvons...
Je recherche l'algorithme O (V + E) pour trouver la réduction transitive avec un DAG. C'est-à-dire supprimer autant d'arêtes que possible de sorte que si vous pouviez atteindre v à partir de u, pour v et u arbitraires, vous puissiez toujours atteindre après suppression des bords. S'il s'agit d'un...
Je crois que cela est vrai, mais je n'ai pas pu obtenir de preuve formelle non plus. Mais est-il vrai qu'un arbre couvrant minimum est accessible en appliquant l'algorithme de Kruskal? De même, est-ce vrai pour l'algorithme de Prim? EDIT: Pour être plus précis, je veux savoir si un MST est donné...
J'ai implémenté un tri topologique basé sur l'article Wikipedia que j'utilise pour la résolution des dépendances, mais il renvoie une liste linéaire. Quel type d'algorithme puis-je utiliser pour trouver les chemins
Je suis un novice (débutant total à la théorie de la complexité computationnelle) et j'ai une question. Disons que nous avons un «problème du voyageur de commerce», l'application suivante des algorithmes de Dijkstra le résoudra-t-elle? À partir d'un point de départ, nous calculons la distance la...
Je lis actuellement l'introduction aux algorithmes et je suis venu de l'algorithme de Johnson qui dépend de s'assurer que tous les chemins sont positifs. l'algo dépend de la recherche d'une nouvelle fonction de poids (w ') positive pour toutes les arêtes et conservant l'exactitude des relations de...
Un graphe orienté est dit unipathique si pour deux sommets et dans le graphe , il y a au plus un chemin simple de à .v G = ( V , E ) u vuuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Supposons que l'on me donne un graphe unipathique tel que chaque bord a un poids positif ou négatif, mais ne contient aucun cycle...
J'ai une question très générique à poser. Elle est liée à la recherche. Je m'intéresse à la théorie des graphes. J'ai fait un cours dedans. J'ai fait quelques sujets liés à la théorie des graphes comme point de vue de le faire en tant qu'étudiant en mathématiques et j'ai également étudié certains...
Étant donné une distribution des degrés, à quelle vitesse pouvons-nous construire un graphique qui suit la distribution des degrés donnée? Un lien ou un croquis d'algorithme serait bien. L'algorithme doit signaler un "non" car aucun graphique ne peut être construit et n'importe quel exemple si...
J'ai un problème et je suppose que c'est NP-difficile, mais je ne peux pas le prouver. Voici un graphique de calque, où le calque 0 est le calque le plus chaud et le calque L le plus bas. il y a un bord dirigé entre les couches, où un bord (A, B) indique que le nœud A peut [couvrir] le nœud B. Et...
Cela pourrait être à la limite de la science cognitive computationnelle, mais je suis curieux de savoir comment le processus suivi par les algorithmes de recherche de chemin commun (tels que A * ) se compare au processus que les humains utilisent dans différentes situations de recherche de chemin...
Existe-t-il un moyen de calculer la taille d'une correspondance maximale dans un graphe biparti non pondéré plus efficacement (par exemple, plus rapidement) que de calculer une correspondance maximale? C'est un plan à long terme, mais c'est souvent un problème intéressant pour éviter des calculs...
Étant donné que l' énumération du chemin - est un problème # P-complet, pourrait-il y avoir des méthodes efficaces qui calculent (ou du moins approximent) la longueur moyenne du chemin - sans les énumérer? Que faire si les chemins sont autorisés à revoir les sommets?ssstttsssttt Des résultats...
Dans un premier arbre de profondeur, il y a les bords qui définissent l'arbre (c'est-à-dire les bords qui ont été utilisés dans la traversée). Il y a des bords restants reliant certains des autres nœuds. Quelle est la différence entre un bord transversal et un bord avant? De wikipedia: Sur la base...
Considérons un graphe orienté GGG sur lequel on peut ajouter dynamiquement des bords et faire des requêtes spécifiques. Exemple: forêt à ensembles disjoints Considérez l'ensemble de requêtes suivant: arrow(u, v) equiv(u, v) find(u) le premier ajoute une flèche au graphe, le second décide si u ↔ ∗ v...
Dans le problème des stations-service, on nous donne villes et des routes entre elles. Chaque route a une longueur et chaque ville définit le prix du carburant. Une unité de route coûte une unité de carburant. Notre objectif est de passer d'une source à une destination de la manière la moins chère...
J'essaie de reproduire les réseaux synthétiques (graphiques) décrits dans certains articles. Il est indiqué que le modèle de Barabasi-Albert a été utilisé pour créer des "réseaux sans échelle avec des distributions de degrés de loi de puissance, PA(k)∝k−λPA(k)∝k−λP_A(k) ∝ k^{-λ} ". PAPAP_A est une...
Pour certains graphiques, les algorithmes de recherche DFS et BFS traitent les nœuds dans le même ordre exact à condition qu'ils commencent tous les deux au même nœud. Deux exemples sont des graphiques qui sont des chemins et des graphiques en forme d'étoile (arbres de profondeur avec un nombre...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...