New answers tagged graphs
1
Yes, $C$ here is the density of (simple) directed graphs. You can see the Wikipedia entry on dense graphs for more details. In this context, total connectivity is just another name for density.
3
The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles.
In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following ...
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
An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^*$ (A-star) algorithm, it was originally designed for just such tasks).
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
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 ...
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 ...
0
You misunderstood the proof of NP-completeness of Subgraph Isomorphism (SI).
We know that SI $\in$ NP because we can check its solution in polynomial time.
Any instance of clique problem (which is NP-complete) can be reduced in polynomial time to some instance of SI. This concludes that any problem in NP can be reduced to some instance of SI.
If you read ...
0
So here is the solution (a little tricky):
Init()
Define a constant M=5.
Initialize n - the number of vertices to be zero.
Initialize 2 arrays A1 and A2 of length M and 2M using the known O(1) triple array "initialization" scheme.
AddVertex()
In each addition, if n < M, do A1[n] = K, and then n++. If n==M then do A2[n] = K, and copy A1[n-M] to A2[n-M] ...
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 ...
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.
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.
0
Do you want a set whose size is a lower bound? Or do you want a lower bound on the size?
If you want a set, does it need to be a subset of a minimum vertex cover, or just a smaller set (in the latter case, any set of the appropriate cardinality would do)?
Since there is a well-known approximation algorithm that is a factor of two over-approximation, you ...
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$.
0
Just do breadth-first search up the graph, colouring each person you meet as being an ancestor of one person or the other, and stop when you reach a person who's an ancestor of both. You should do the searches in parallel (one generation back on one person, then one generation back on the other, and so on) because any common ancestor will be approximately ...
0
With obstacles, you can use an algorithm as it is used for routing the shortest car distance. The idea is that you perform a search not breadth first, but with moves first that get you closer to the target. And you start from both ends and meet in the middle.
Define the "optimal distance" between points as the distance given by the algorithm for lowest ...
0
Without obstacles you can solve this in constant time. You'll have to work the details out, but the idea is that in two moves if you want to cover distance you can move 4 steps in one direction and 0 or 2 in the either, or 3 steps in each direction. So let's say the distance is (100, 48): You do 24 double moves (4, 2) plus 1 double move (4, 0). Let's say the ...
0
A bit old post yet I guess some one might benefit from this reply. I tried to solve for the simpler graph of 12 vertices. This graph is more symmetrical and hence easier (but the method might be applicable to the 25 vertex one too).
Steps (look at earlier reply for vertex numbering)
Build a path of length 10 (max path length; see previous replies too) ...
0
Circles centers form isosceles triangle with base of length $2r$ and arms of length $R+r$, so
$ \tan (\frac{\beta}{2}) = \frac { r}{ r+R} $ hance $\beta = 2\arctan(\frac{r}{r+R}) $
Top 50 recent answers are included
