# Tag Info

166

Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing. The reason you don't usually ...

47

No, consider the complete graph $K_4$: It has the following edge-disjoint spanning trees:

42

There are two cases: $P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we ...

42

Graphs are definitely one of the most important data structures, and are used very broadly Optimization problems Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination. The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem) Chess, ...

40

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality). If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a ...

37

Recalling that a directed graph is a graph where the edges have an associated direction with them. Using a directed graph you can represent asymmetrical relationships between nodes, while in undirected graph we can represent only symmetrical relationships. Practically, using a directed graph you can represent: Road networks (using a directed graph you ...

34

The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows. Suppose that we are trying to solve the maximum flow problem for the following network $G$ (where each label $f_e/c_e$ denotes both the flow $f_e$ pushed through an edge $e$ and the capacity $c_e$ of this edge): One ...

25

Adding a weight to every edge adds more weight to long paths than short paths. (Long in the sense of having many edges.) For example, suppose the lowest-cost edge has weight $-2$ and there are two paths from $a$ to $b$: a single edge of weight $3$ and a path with two edges, each of weight $1$. The two-edge path has the lowest weight. ...

25

Pathfinding is arguably one of the most practical subareas of algorithms and graphs. I am sure you can find plenty of use cases from navigation, routing, logistics and computer games, all growing multimillion businesses. If you want to think about social networks, you might think about recommender systems some of which are graph-based for discovering ...

24

Yes, there is a difference between the three terms and the difference can be explained as: Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. 18 / \ 15 20 / \ 40 50 / \ 30 50 Complete Binary Tree: A Binary Tree is complete ...

23

Probably the easiest way to enumerate all non-isomorphic graphs for small vertex counts is to download them from Brendan McKay's collection. The enumeration algorithm is described in paper of McKay's [1] and works by extending non-isomorphs of size n-1 in all possible ways and checking to see if the new vertex was canonical. It's implemented as geng in McKay'...

23

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes. Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M[i][j] = 1$ if there is edge between ...

23

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue. The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always ...

20

A 3-clique can be found in an $n$-vertex graph $G$ in time $O(n^\omega)$, where $\omega < 2.376$ is the matrix multiplication exponent, and in $O(n^2)$ space by a result of Itai and Rodeh [1]. Basically, they show that $G$ contains a triangle if and only if $(A(G))^3$ has a non-zero entry on its main diagonal. Because a triangle is also a cycle $C_3$, one ...

19

Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent anything in the real world, for example, the amount of money to be transferred from one account to another account. The amounts can be positive or negative. For example, if you want to go from $a$ to $b$ in your graph while losing as less money as possible (...

19

FOR x := 1 TO n DO FOR y := 1 TO n DO FOR z := 1 TO n DO IF E(x,y) && E(y,z) && E(z,x) THEN REJECT ACCEPT Each of the variables x, y and z requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.

18

BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first_search Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F. In an unweighted graph, you can use BFS to search for the shortest path from A to all other nodes in the same run too! (just don't make it stop as soon ...

18

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$. In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.

18

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory. An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with ...

17

This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, this converges either to a fixed point or to a cycle of length 2; see for example pages 5-6 of Ginosar and Holzman's The majority action on in nite graphs: ...

17

You seem to have a misunderstanding of generative models v.s. "recognizing" models. The grammar you have on the right generates words by applying rules, starting from the initial variable, and stopping after there are no more variables. Automata, however, recognize a language as follows: you feed the automaton a word, letter by letter, and the automaton ...

17

A complete graph is a graph with every possible edge; a clique is a graph or subgraph with every possible edge. That is, one might say that a graph "contains a clique" but it's much less common to say that it "contains a complete graph".

17

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that induces a triangle. If you reach past the last 3-tuple then the graph contains no triangle and you can accept.

15

One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost ...

15

The type of argument you are looking for is as follows: If graph isomorphism were NP-complete, then some widely believed complexity assumption fails. There are at least two such arguments: Schöning showed that if graph isomorphism is NP-complete then the polynomial hierarchy collapses to the second level (equivalently, $\Sigma_2^P = \Pi_2^P$). Babai's ...

14

If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.

14

For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees. For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that ...

13

Make a BFS/DFS traversal on the graph. If you visited every vertex then it is connected otherwise not. Note: You have to apply BFS/DFS only one time on the graph

13

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts. An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the ...

13

Yes, there are even algorithms which are able to satisfy additional constraints. It can occur as a subtask during mesh generation. The vanilla algorithm is the Delaunay triangulation, which is closely related to the Voronoi diagram (in case you wonder why D.W. thinks that the Voronoi diagram answers your question).

Only top voted, non community-wiki answers of a minimum length are eligible