An undirected graph has edges which have no orientation. It is a mathematical concept.
Definition of an undirected graph.
Questions tagged [undirected-graph]
271 questions
9
votes
1 answer
Count number of pairs of nodes in undirected graph such that W - L >= K
Question:
Given an undirected graph of N nodes and N-1 edges. The length of all edges are 1. Each edge i has a weight of Wi. (0 <= Wi <= 10.000)
The graph is guaranteed to not have any loops. So there's always one (and only) shortest path between 2…
unglinh279
- 675
- 4
- 24
9
votes
2 answers
Topological sort on directed and undirected graphs using DFS algorithm
I can determine the topological sort of a directed graph using DFS algorithm. If there are no cycles, I assume the topological order I found is valid. If there is a cycle, I assume the topological order is useless. Am I correct so far?
What about…
Mehmed
- 2,880
- 4
- 41
- 62
6
votes
1 answer
How to find if there is a simple path from vertex x to vertex y that includes the edge e
so I faced this question and I hope that someone can help me in it.
Given an undirected graph G = (V, E), 2 vertices x,y and an edge e = (v,u).
Suggest an algorithm to find if there's a simple path from x to y that includes the edge e.
So the focus…
Mohamad S.
- 199
- 1
- 9
6
votes
1 answer
Finding equally-sized mutually exclusive complete subgraphs within a graph whose union is the entire graph
INPUT
Undirected graph G with n vertices and an integer k such that k divides n.
The set of all vertices will be denoted by V.
OUTPUT
A set S of sets of vertices such that:
S has k elements
Each element of S is a complete subgraph in G (all…
ChocolateDrops
- 61
- 4
5
votes
1 answer
How can I find bridges in an undirected graph?
Given an undirected Graph, how can I find all the bridges? I've only found Tarjan's algorithm which seems rather complicated.
It seems there should be multiple linear time solutions, but I can't find anything.
Jakub Arnold
- 85,596
- 89
- 230
- 327
4
votes
2 answers
Test data has all possible edges in every community in an undirected graph
I am working with a list of edges in R:
data <- structure(list(var1 = c("a", "b", "c", "d", "f", "g", "h"), var2 = c("b",
"c", "a", "e", "g", "h", "i")), class = "data.frame", row.names = c(NA,
-7L))
> data
var1 var2
1 a …
Giulio Centorame
- 678
- 4
- 19
4
votes
0 answers
Is there a name/algorithm for this graph problem? Expand a grid outward to collect maximum value on edges
I'm facing an undirected weighted graph problem that I'm sure has been tackled many times, and I'm wondering if it has a name and existing algorithm. Edges represent value I want to capture and maximize, starting from a subgrid and expanding outward…
Ben Hendel
- 51
- 4
4
votes
0 answers
Calculating a threshold based on the connectedness of a weighted graph
Given a matrix like the one that follows (but a lot bigger) that describes a weighted undirected graph,
structure(list(from = c("TPM1", "TPM1", "TPM1", "TPM1", "TPM1",
"TPM1", "TPM1", "TPM1", "TPM1", "TPM1", "TPM1", "TPM1", "TPM1",
"TPM1", "TPM1",…
J. Doe
- 619
- 4
- 16
4
votes
3 answers
Numpy- get neighbors matrix from 2D array
I have a undirected graph given by:
A,B
A,C
A,F
B,D
C,D
C,F
E,D
E,F
And I need to transform this to a matrix N where
N[x,y] = 1 if x is neighbor of y (like A and B) and 0 if not
What is the fastest way to do it?
NOTA The graph is stored as numpy…
farhawa
- 10,120
- 16
- 49
- 91
3
votes
1 answer
Efficient method for finding unique neighbors of nodes in an undirected graph without using Matlab built-in functions
I have an undirected graph of N nodes and L links, whose structure is typically described by its adjacency matrix A with N rows and N columns. In this adjacency matrix, the value '1' denotes a link between two nodes and, conversely, '0' denotes no…
Grasshoper
- 457
- 2
- 13
3
votes
1 answer
"sna" or "igraph" : Why do I get different degree values for undirected graph?
I am doing some basic network analysis using networks from the R package "networkdata". To this end, I use the package "igraph" as well as "sna". However, I realised that the results of descriptive network statistics vary depending on the package I…
Edda
- 33
- 2
3
votes
1 answer
Finding maximum number of nodes in set of undirected graphs
I have a set of nodes (N=7)
{a, b, c, d, e, f, g}
These nodes form one or more distinct undirected graphs, I want to find the graph with the maximum number of nodes. However, I have a constraint that the complexity can not be more than (N*M) where…
maracuja
- 417
- 8
- 24
3
votes
1 answer
How to compare edges in a graph to implement a triadic closure like in network graphs like facebook
I am trying to implement a graph that contains Vertices(nodes) that relate to a Profile class(like a Facebook profile but more mediocre). Each of the vertices(Profiles) is stored in a Binary Search Tree which is then loaded or stored in an…
Brevyn Kurt
- 41
- 5
3
votes
3 answers
Find the reverse direction edge and subtract its weight from its oposite
I'm having a matrix like the following one
m <- expand.grid(LETTERS[1:24],LETTERS[1:24])
m$weight <- runif(nrow(m), 0.01, max = 1)
m <- m[m$Var1!=m$Var2, ] ##remove loop edges
colnames(m) = c("to","from","weight")
and in this form it describes a…
J. Doe
- 619
- 4
- 16
3
votes
2 answers
Count number of nodes in each connected part of an undirected unweighted graph
I am new to C++ STL and have started Graph Theory recently.
After referring to https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/, I can count the number of connected components in an undirected, unweighted graph using DFS…
Tanya Sethi
- 33
- 1
- 8