# Tag Info

## Hot answers tagged graphs

Accepted

### Is zero allowed as an edge's weight, in a weighted graph?

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 ...
• 81.9k
Accepted

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

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

### Residual Graph in Maximum Flow

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 ...
• 3,724
Accepted

### What are some real world applications of graphs?

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 ...
• 556
Accepted

### Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

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 ...
• 29.8k

### Example of a graph with negative weighed edges in which Dijkstra's algorithm does work

Take a look at the simplest possible example: Our graph has only two nodes: $s,t$, and a single edge between them. In this example, it won't matter what is the cost of this single edge (it can be ...
• 11.6k
Accepted

### Why are directed graphs important?

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 ...
• 864

### Real life examples of negative weight edges in graphs

Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that ...
• 16.7k
Accepted

### Is there a difference between perfect, full and complete tree?

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 ...
• 456
Accepted

### Why are graphs represented as adjacency lists instead of adjacency sets?

In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms. In the cases where we only need to enumerate ...
• 16.7k

### What are some real world applications of graphs?

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 ...
• 22.6k

### Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...
• 16.7k

### When are adjacency lists or matrices the better choice?

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. ...
• 9,837

### Does the Minimum Spanning Tree include the TWO lowest cost edges?

For simple graphs*, it is true for the following reason: Kruskal’s algorithm is correct Kruskal’s algorithm works as follows: sort the edges by increasing weight repeat: pop the cheapest edge, if it ...
• 16.7k

### What is the meaning of 'breadth' in breadth first search?

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 ...
• 986

### Is Group Theory useful in Computer Science in areas other than cryptography?

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, ...
• 3,543