Questions tagged [graph-theory]
A graph is a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. Graphs can be undirected or directed, where edges are directed, indicating from which vertex they start and to which they lead ( be it other or the same ).
graph-theory
4,494
questions
4
votes
1
answer
53
views
creating hexagonal lattice graph in networkx
I need to create a hexagonal lattice network based on another researcher's work. The researcher describes describes the structure of their network in the yellow highlighted section of text here.
Here'...
- 1,021
-1
votes
0
answers
37
views
why isnt my bridge finding DFS implementation working? [closed]
def find_bridges(self,n,low_link,visited=list(),back=list(),bridges=list()):
def get_low_link(x):
return low_link[visited.index(x)]
if n[0] not in visited:
...
1
vote
3
answers
73
views
Find number of redundant edges in components of a graph
I'm trying to solve problem 1319 on Leetcode, which is as follows:
There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai,...
- 11.5k
1
vote
0
answers
39
views
Rewiring strategies to obtain networks with desired clustering coefficient and average path length
There have been a few questions (and subsequent answers) regarding the generation of connected networks (graphs) with a fixed edge density (see e.g., here and here), and these are mostly based on the ...
5
votes
1
answer
98
views
Minimal path on weighted tree query
Given a weighted tree with n vertices. there are q queries and for each query, you are given integers (u,k). find number of vertices v such that the smallest edge on the route from u to v is equal to ...
0
votes
1
answer
44
views
What is the complexity of the following code? Is it O(n^3log(n))?
What is the complexity of the following code? Is it O(n^3log(n))?
#G is an undirected dense graph, which has N vertices.
import networkx as nx
def cal_minimax_path_matrix(G):
MST = nx....
1
vote
3
answers
169
views
Get the most optimal combination of places from a list of places through graph algorithm
We are having a networking situation where he have four nodes - say A, B, C and D. The problem - A, B, C and D are not fixed, but have a bunch of possibilities.
Say A can have values A1, A2 upto An.
...
- 5,003
4
votes
2
answers
263
views
Minimum edges to form path with length L
I came across this problem.
Given a weighted tree T, find the minimum number of edges to form a simple path (no duplicate vertices or edges) of weight (sum of weights of edges) exactly L.
More ...
- 146
2
votes
2
answers
92
views
Linear time algorithm for computing radius of membership hyper-sphere
We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E.
Alongside the ...
- 542
3
votes
3
answers
218
views
How to find all simple paths of no more than k lengths starting at a vertex in a directed graph?
I am trying to find all simple paths up to a given length, and working on using BFS to solve this problem. However, I am not sure about the specific algorithm to use. It seems that BFS cannot easily ...
- 55
1
vote
2
answers
49
views
Delete from child table on update of parent row with composite foreign key
For reasons outside of my control I am trying to build a graph-like data structure in PostgreSQL. The business requirement is that everytime a node changes, its edges need to be re-computed. Also, ...
- 1,461
0
votes
0
answers
80
views
Maximum Sum of Vertices in DAG Excluding Directly Connected Vertices
How can I calculate the maximum possible sum of vertices in a weighted DAG excluding vertices directly connected by an edge? This is a vertex selection problem where each vertex has a weight.
In this ...
- 185
0
votes
1
answer
46
views
Spanning disjoint trees in directed bipartite graphs
Assume we have a directed bipartite graph G with two partitions, A and B. All the edges are assumed to start from A and end in B . Assume that every vertex has at least one adjacent edge. I want to ...
- 1
4
votes
1
answer
96
views
How to calculate the length of cycles in a graph using parallel algorithms in C?
I am getting desprite, because I can't solve this problem. I hope this is the right place to ask for help in this context.
The Problem is, that I have a graph that is the union of disjoint directed ...
- 41
1
vote
1
answer
37
views
How do I run the Bipartite Matching and Min Vertex Cover Algorithms on this graph?
Hi, so I am supposed to run the Bipartite Matching and Min. vertex cover Algorithms on this graph (with s = 0 and t = 6) using Ford-Fulkerson and DFS/BFS, "breaking ties in favor of the smaller ...
- 67