3
If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge , then $G$ is connected.
No, it is not true. Here is an counterexample.
Graph made at https://graphonline.ru/en/
Exercise. Construct a simpler counterexample where $|V|=n$ and $|E|=n-1$.
3
First, $|V|$ is the number of vertices and $|E|$ is the number of edges.
The point is that if a graph is connected it must have at least $|V|-1$ edges. Therefore, $|V|\leq |E|+1$, so
$$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$
Writing $|V|=O(|E|)$ is something of an abuse of notation. $O(\cdot)$ is an asymptotic statement about ...
3
No. A graph with only the edges of a polygon has an Hamilton circle, but the degree of each vertex is 2.
2
You've exactly described the first situation, i.e. we indeed say that $u$ and $v$ are non-adjacent. For the second we do the same, but we want to also specify they are in the same component of $G$ which contains them if $G$ is not connected.
These are already simple and well-understood descriptions and there's nothing "more standard". However, you are also ...
1
You can do one graph traversal to find all the connected components of your graph.
Then add an edge from each connected component to the next : the graph is fully connected and you did only one traversal, that's $O(n^2)$
1
I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices.
Having the following DAG.
If we want to merge node A and B. We add a new node which has the similar attributes as A + B.
Then trasverse from new node AB (should be Depth-first):
If it find Node A or B, then the merge should ...
1
Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic.
I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and ...
1
Make a Node class whose objects hold and an array of references to the other nodes they connects to. Make a Graph class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.
1
Bellman-Ford simply returns there exists at least one negative-weight cycle, it doesn't actually find all edges part of all such cycles. At best, without extending the algorithm too much, you find at most one edge per negative-weight cycle as cycles may intersect. There are ways to recover a negative weight cycle, see the link you provided, but this is ...
1
Hamiltonian path problem remains NP-complete in planar graphs [1], so your problem is also NP-complete since in a planar graph, two edges cannot intersect with each other.
[1] Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.
1
Your algorithm returns a cycle rather than a path.
Here is a cycle:
Here is a path:
(Both images taken from Wikipedia.)
To get a path from the cycle, simply remove one edge (this is my best guess for what return a path of that cycle means).
Let me also mention that your algorithm is very inefficient. A much better choice is to use BFS/DFS.
Only top voted, non community-wiki answers of a minimum length are eligible
