Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

0
votes
1answer
15 views
0
votes
0answers
33 views

Convert undirected graph to directed graph with specific condition

undirected graph is given which has M edges and N vertices we have to convert every edge from u-v to u->v or v->u such that indegree of every vertex is even.Which method or algorithm is suited for ...
1
vote
1answer
29 views

Graph theory: determining maximum number of edges

Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful ...
1
vote
0answers
17 views

Enumerate all re-convergent paths in a digraph (with cycles)

I'm looking for an algorithm to count and enumerate (separately, if differing complexity) all the reconvergent pathsets in a simple, directed, non-weighted graph, which may contain cycles. That is, ...
1
vote
0answers
16 views

Proving there is no polynomial algorithm for independent set

I need some guidance in an assignment I'm doing. I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
2
votes
2answers
41 views

Prove that the number of edges is at least twice the number of vertices

I need to prove that In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices. I already know that $\deg(n) = ...
0
votes
0answers
16 views

Finding shortest cycle in graph with positive weights

Given a graph G, with all positive weights, find the shortest cycle length in O(V^3) My idea is, negate al the edges, apply floyd-warshall algorithm and then for all $i$, find the largest $M[i][i]$ ...
3
votes
1answer
35 views

Strongly connected orientations of undirected graphs

I'm trying to prove the following. There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge. (An orientation of an undirected ...
3
votes
1answer
22 views

How to calculate the minimum number of groups, by grouping groups with capacity together?

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem. If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
1
vote
2answers
20 views

MST Proof (Kleinburg & Tordos)

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in ...
0
votes
0answers
39 views

Graph Implementation Problem - Shortest Path/Dijkstra's (?)

Have this small graph problem to do for today, was wondering if anyone had any possible solutions/insight for it. Given two containers, one of which can accommodate a liters of water and the other b ...
3
votes
2answers
52 views

Calculate the number of cycles of a Cactus graph?

Considering a cactus graph $G = (V, E)$, defined as: A graph is a cactus if every edge is part of at most one cycle. There is a way to calculate the number of cycles in this graph given only $n= |...
-1
votes
0answers
15 views

Pseudocode of calculating an Euler tour

In the context of Christofides' algorithm, not that I think it matters. How do you calculate an Euler tour? context: https://en.wikipedia.org/wiki/Christofides_algorithm#example This is what I think ...
0
votes
0answers
11 views

Difference between Graph clustering and Node clustering

I have confused with Node clustering and graph-clustering, what is the difference? Can anyone help me to distinguish these two properly with small examples?
21
votes
5answers
3k views

Do any two spanning trees of a simple graph always have some common edges?

I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
1
vote
2answers
24 views

Minimum number of components in graph

Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only ...
0
votes
0answers
12 views

Number of automorphisms 4 cyclic graphs with one vertex in common has?

Number of automorphisms 4 cyclic graphs with one vertex in common has? I know that cyclic graphs Cn, n is number of vertex, have 2*n automorphisms. So I think the solution is 2(n-1). Correct?
2
votes
1answer
83 views

Does a Vertex Cover exist?

This should be a simple question, but I am a little bit confused. A proof on page 556 of Algorithm Design says: "Let $e=(u, v)$ be any edge of $G$. The graph $G$ has a vertex cover of size at most $...
0
votes
0answers
8 views

How do I extend bellman-ford, to limit the number of edge-traversals (k), that are permitted?

How do I extend this bellman-ford, so I can limit the number of edge-traversals (k), that are permitted? And no, it's not just a matter of limiting the outer loop to run k times, since BF updates ...
-4
votes
0answers
39 views

ACM Swiss Subregional Contest Graph Problem [closed]

I am not sure how to find a solution to this problem that runs within the time limit. Edit: what I’m asking for is a solution whose complexity is on the order of V+E (judging from the time limit) ...
0
votes
0answers
22 views

Help with understanding Kleitman–Wang algorithm

I have a problem in which I need to solve the realization for a directed graph when I am given the in and out degrees for n number of vertices. A hint was to use network flows. I know that the ...
1
vote
0answers
19 views

(Formal) Proofs of Node Centrality Properties

Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to ...
0
votes
2answers
34 views

Formula for finding number of colors to color a map such that no two adjacent counties have the same color

Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?
0
votes
1answer
17 views

Minimum perfect matching with uneven vertices?

Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?
1
vote
1answer
98 views

Need help to come up with definitive proofs with regard to Planar Graphs

I was working through a few problem sets and came across this question Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle ...
1
vote
0answers
11 views

Can Description Logic be expressed by compiler type systems?

The Semantic Web defines standardised logic under the OWL DL standard. Programming languages such as OCamel and TypeScript support type inference and algebraic types. What are the difference between ...
0
votes
0answers
11 views

How to denote a graph class which allows only $k$ instances of a certain induced subgraph?

Suppose that a graph class $\mathcal{C}$ is defined as follows: A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal, but has at most $k$ $5$-cycles. I am aware that the ...
2
votes
1answer
34 views

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
0
votes
0answers
16 views

Maximization Modularity using SDP relaxtion

I am trying to clustering the graph by maximizing modularity where modularity is given by: $Q=\frac{1}{2m} \sum \limits_{i,j}\left(A_{ij} - \frac{d_i d_j}{2m}\right)\delta(c_i,c_j)$ or equalvance ...
0
votes
0answers
12 views

Decide if there exist two vertex set $V_1$ and $V_2$ ($V_1 +V_2 = V$) such that both $V_1$ and $V_2$ are vertex cover

Given a graph $G$ and its vertex set $V$. Considering the following problem: are there two disjoint vertex sets $V_1$ and $V_2$ ( $V_1 \cup V_2 = V$) such that both $V_1$ and $V_2$ are vertex covers ...
2
votes
1answer
96 views

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance) $\alpha$ denotes the start and end vertex of ...
0
votes
1answer
57 views

Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

What is the complexity of this problem EULERIAN ARC REVERSAL Input: a directed graph $G(V,A)$ and an integer $k$ Output: YES if $k$ arc reversals are enough to transform $G$ into an ...
1
vote
0answers
43 views

Name for the tree formed after collapsing cycles

What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)? For instance, the digraph (given by an NFA; ignore edge labels please) below becomes ...
1
vote
0answers
47 views

Graph with two classes of nodes A and B: densest subgraph with same node classes cardinality

I'm searching (without results) a problem that can be reduced to finding the densest subgraph with the same cardinality between two classes of nodes. Consider a graph with nodes of class A and nodes ...
-1
votes
0answers
16 views

Is there a path between a and b, including the true marked edges and excluding the false marked ones? (Connected Finite Graphs)

I have a connected, finite, undirected graph topology. It can be anything satisfying these properties. I select some edges, the constraint is that; I need to traverse these edges that I marked 'true',...
0
votes
0answers
25 views

How to convert the result of a linear program in to graph path?

I would like to know how can I convert the result of a linear program into a graph path. For example, I am using CPLEX in Python to solve multicommodity flow problems, where it assigns a portion of ...
2
votes
2answers
58 views

Proof for BFS and DFS equivalence

I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases. Let $G$ be a directed ...
0
votes
0answers
12 views

What are “self-adjusting computation” and “dynamic programming”, and how are they different?

According to this website: Self-adjusting computation refers to a model of computing where computations can automatically respond to changes in their data The papers linked on this page make ...
4
votes
1answer
19 views

In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?

When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs. I am confused about the definition of an $S_3$ graph....
0
votes
0answers
21 views

Bellman-Ford shortest path [duplicate]

I've been trying to prove that if I'm given a directed weighted graph with no negative cycle, then there exist an order on the edges such that after the first iteration I will get the shortest paths. ...
0
votes
0answers
38 views

In a directed graph G, detect if there is a path that visits each node at least once

I'm trying to prove that Given a directed graph G,we can't detect if there is a path that visits each node at least once, I’m trying to use the fact that: detecting if a directed graph has a Hamilton ...
1
vote
1answer
28 views

Variant of an approximation algorithm for vertex cover

Here is an approximation algorithm that finds vertex cover of a graph. ...
3
votes
1answer
57 views

Christofides algorithm (by hand)

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example The graph: [![enter image description here][1]][1] ...
2
votes
1answer
30 views

minimum number of nodes that traverse all the graph

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
0
votes
0answers
17 views

Modelling the following Entscheidungsproblem as the flow network problem

We have sensors that collect data and send them from time to time as packet to a center node in the network.We want to study if we can achieve that in T steps.So let´s consider a graph G=(V,E) a ...
1
vote
0answers
37 views

Preferring forward edges to cross edges during graph DFS traversal

It's well known that depth-first search order of a graph is (usually) not unique, and multiple orders are possible depending on the order in which successors are processed for each node. Let's ...
1
vote
1answer
18 views

Chinese postman problem, but criteria = visit each vetex at least once

Chinese postman problem, but where the postman have to visit each vetex at least once. Is there a name for this problem? What is the ideal algorithm to solve this problem?
2
votes
1answer
31 views

Minimum cost node cut

I am interested in solving the following problem: Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph. Is there ...
3
votes
1answer
36 views

Why is dominating set in $W[2]$, but independent set in $W[1]$

In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape ...
1
vote
1answer
34 views

proof that BFS remains total after adding edge to graph

I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$). The inductive proof consists in 2 cases: (i) Prove that $\rm{BFS}$$(u \in \...