# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

2,241 questions
Filter by
Sorted by
Tagged with
14 views

### Network density vs connectivity

I was reading this paper where they mention about undirected networks: "The total connectivity of a network is defined as $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total ...
63 views

### communities problem with union and find

I am trying to solve the following problem: Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry ...
38 views

### What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
371 views

### Finding all unique paths from a source to a sink in a specially-formed DAG

Let $G$ be a directed, acyclic graph of order $n$, such that: $G$ has exactly one source vertex $s$; $G$ has exactly two sink vertices $t_1, t_2$; The out-degree of any non-sink vertex in $G$ is ...
29 views

13 views

### efficiently calculate nearest common ancestor in a family tree (each person has two parents)

I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent). Just iterate back to root for each ...