Donné est un graphe planaire et soit dénoter son encastrement dans le plan st chaque arête a la longueur . J'ai en outre un ensemble de points où chaque point est contenu dans . De plus, il tient pour tout point dans qu'il existe un avec une distance géodésique à au plus un. (La distance est...
J'ai étudié les trois et j'énonce mes inférences ci-dessous. Quelqu'un pourrait-il me dire si je les ai suffisamment compris ou non? Je vous remercie. L'algorithme de Dijkstra est utilisé uniquement lorsque vous avez une seule source et que vous souhaitez connaître le plus petit chemin d'un nœud à...
Je connais très bien Dijkstra et j'ai une question spécifique sur l'algorithme. Si j'ai un énorme graphique, par exemple 3,5 milliards de nœuds (toutes les données OpenStreetMap), je ne pourrais clairement pas avoir le graphique en mémoire, donc le graphique est stocké sur disque dans une base de...
Le problème de clique est un problème complet de bien connu NPNPNPoù la taille de la clique requise fait partie de l'entrée. Cependant, le problème de k-clique a un algorithme de temps polynomial trivial ( O(nk)O(nk)O(n^k) lorsque kkk est constant). Je m'intéresse aux bornes supérieures les plus...
Je faisais des exercices de programmation dynamique et j'ai trouvé l'algorithme Floyd-Warshall. Apparemment, il trouve les chemins les plus courts de toutes les paires pour un graphique qui peut avoir des bords de poids négatifs, mais pas de cycles négatifs. Donc, je me demande quelle est la...
J'essaie de trouver une méthode efficace pour détecter si un graphe donné G a deux arbres de recouvrement minimal différents. J'essaie également de trouver une méthode pour vérifier si elle a 3 différents arbres couvrant minimal. La solution naïve à laquelle j'ai pensé consiste à exécuter...
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...
Laissez GGG un graphe, et que sss et ttt deux sommets de GGG . Pouvons-nous échantillonner efficacement un chemin sss - plus court de tttmanière uniforme et indépendante au hasard dans l'ensemble de tous les chemins les plus courts entre sss et ttt ? Pour simplifier, nous pouvons supposer que GGG...
J'essaie de résoudre un problème de graphique (ce n'est pas pour les devoirs, juste pour pratiquer mes compétences). Un DAG est donné, où est l'ensemble des sommets et les arêtes. Le graphe est représenté comme une liste d'adjacence, donc est un ensemble contenant toutes les connexions de . Ma...
J'essaie de prouver qu'un arbre binaire avec nnn nœuds a au plus ⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceilfeuilles. Comment pourrais-je procéder avec l'induction? Pour les personnes qui suivaient la question initiale sur les tas, elle a été déplacée ici
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...
J'ai besoin de construire un graphique d'expansion d-régulier pour quelques petits d fixes (comme 3 ou 4) de n sommets. Quelle est la méthode la plus simple pour le faire dans la pratique? Construire un graphique aléatoire régulier, qui s'est avéré être un expandeur? J'ai également lu sur les...
Certaines œuvres de Conor McBride, Diff , Dissect , relient la dérivée des types de données à leur "type de contextes à un trou". Autrement dit, si vous prenez la dérivée du type, vous vous retrouvez avec un type de données qui vous montre à quoi ressemble le type de données de l'intérieur à un...
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...
Quelles sont les principales différences entre ces trois termes isomorphisme, automorphisme et homomorphisme dans un langage simple profane et pourquoi nous faisons isomorphisme, automorphisme et
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...
É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...
Considérons un graphe . Chaque arête a deux poids et . Trouvez un arbre couvrant qui minimise le produit . L'algorithme doit s'exécuter en temps polynomial par rapport à.G(V,E)G(V,E)G(V,E)eeeAeAeA_eBeBeB_e(∑e∈TAe)(∑e∈TBe)(∑e∈TAe)(∑e∈TBe)\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in...
Prenons un carré, ABCD. Il m'a semblé intuitivement que son polynôme chromatique est où il y a des couleurs disponibles.λ(λ−1)(λ−1)(λ−2)λ(λ−1)(λ−1)(λ−2)\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)λλ\lambda C'est-à-dire qu'il y a façons de choisir une couleur pour A, il y a façons pour les...
Il existe une famille de graphes aléatoires à nœuds ( due à Gilbert ). Chaque bord possible est inséré indépendamment dans avec une probabilité . Soit le nombre de cliques de taille dans .nG(n,p)G(n,p)G(n, p)nnnp X k k G ( n , p )G(n,p)G(n,p)G(n, p)pppXkXkX_kkkkG(n,p)G(n,p)G(n, p) Je sais que...