Questions tagged as 'grafo'

Tagged questions
1
answer

What is the main difference between the Knuth-Morris-Pratt and Boyer-Moore algorithms

I know that KMP (Knuth-Morris-Pratt) is used to find a text Y in X, tries to set a pattern in Y, and then saves this pattern in a vector. And I also know that BM (Boyer-Moore) works best for small words. But what is the main difference in...
asked by 22.08.2017 / 15:30
1
answer

Is it possible to use coloring of vertices, edges or faces in a DIRECTED graph?

Would you like to know if you can use the coloring technique in targeted graphs? If yes or no, why?     
asked by 05.06.2015 / 14:32
2
answers

Graph possible paths python

I have a dictionary, where the key is a vertex and the value is a list of vertices adjacent to the vertex (key). dic = {'A':['B,'C'],'B':['A','C','D'],'C':['A','B','D'],'D':['B','C']} What I want is an array of all possible paths (from one...
asked by 05.06.2015 / 01:57
1
answer

Search for isolated components in graph

What will be the best algorithm to find isolated components in a graph? That is, components that do not lose information. Inthisimage,theonlycomponentisolatedisH,becauseitonlyreceives"information".     
asked by 04.03.2014 / 04:56
1
answer

Kruskal Algorithm problem C ++

I'm implementing the Kruskal algorithm, but I'm having a problem because it's losing one of the links and its value, I already did an implementation in Dijkstra, but in the work I'm doing, Kruskal is the best one to be done, I'm not finding the...
asked by 27.06.2015 / 05:26
0
answers

Christofides Algorithm - TSP, Problem in transforming AGM into a graph with all vertices of even degree

I'm implementing the Christofides algorithm and I'm getting the data from TSPLIB. the Christofides Algorithm has the following steps: Finding the Minimum Generation Tree Find all odd vertices (an even number of vertices) Find the perfect...
asked by 07.06.2018 / 17:25
1
answer

Doubt in the implementation of the deep search in Graphs

I am studying for an algorithm test and I ended up finding some problems implementing the DFS ( Depht-First Search / depth search) > Stack . static void emProfundidade(ArrayList<Node> grafo, Node origem) { Stack<Node> pilha...
asked by 28.06.2015 / 05:16
1
answer

Search in graphs to solve the theorem of euler

Hello, I would like some help to do a search on a graph and check if it satisfies the euler theorem. Theorem says: " A connected graph will contain an Euler cycle if, and only if, each of the vertices has an even number of edges falling on it...
asked by 24.08.2016 / 18:07
2
answers

How to associate objects to the vertices of a graph?

I am studying about graph theory, more specifically about the vertices that are units representing a given node of a graph. However, there are still some questions about the vertices. See this illustration graph in Python: graph = { 'A'...
asked by 14.08.2018 / 02:02
1
answer

"Join" two graphs in R

I'm using the igraph library to create two graphs in the R: g.v1 <- graph.full(6, directed= TRUE) E(g.v1)$weight <- 1 g.merchant <- graph.empty(1, directed=TRUE) E(g.merchant)$weight <- 1 This two graphs, g.v1 and...
asked by 06.10.2016 / 15:41