# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,455 questions
Filter by
Sorted by
Tagged with
329 views

### Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

The problem concerns finding shortest paths in graph from a single source to a single destination. So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
1 vote
24 views

### Split Bipartite Graph

I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
49 views

### Finding a Hamiltonian Cycle in a directed graph - graph problem

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
37 views

### Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $n^{k-1}$ I've tried this formula on an example ...
10 views

### Approach for flattening a 3-d cube given cuts

Take a cube. Cut seven of its edges. Consider a graph whose vertices are the centers of the faces of the cube. If two faces share a common edge, then the graph also has an edge connecting the two ...
17 views

### How to make this directed graph DFS algorithm search an undirected graph DFS still using adjacency list? [closed]

for example if I pass 5 to the below program, it will print the nodes from the edges in green (see image below), but it won't print the ones in red ...
30 views

### Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
72 views

### Name and complexity of this problem on bipartite graphs

Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes. I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...
28 views

### Wrong Solution for Spanning tree with chosen leaves problem

Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ ...
22 views

### Using an undirected graph to represent an ordered pair?

Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
Let $G = (V, E)$ be an $n$-vertex complete bipartite graph with vertex bipartition $(L, R)$ with $|L| = |R|$, and an integral cost function $c : E → N$ on the edges. For a perfect matching $M ⊆ E$, ...