What is a Graph?
A graph is a data structure composed of nodes(vertices) and edges. Simple, I know. Not enough to solve the mysteries of the world but quite a lot of ubiquitous software would be redundant without it. For those of you participating in SOF Olympiads, imagine finding your SOF second level center without Google Maps.
Among its many uses, graphs are used to establish relationships between friends on Facebook where users are nodes and edges are present between pairs of users who are friends. Graphs are also an essential part of navigation software(hello Google Maps) where places are nodes and the roads are edges. This brings us to a very important aspect of graphs – graph theory, which consists of many useful algorithms to utilise graphs to their full extent. In the case of maps, for example, we use an algorithm to find the shortest distance between two nodes(it isn’t actually this simple but it is one of the parameters other than traffic, blockages etc). Watch this space to know more about simple algorithms related to graph theory.
Coming soon: Articles regarding uses of and simple algorithms related to graph theory
Nodes and Edges
Nodes are the fundamental units of graphs. It might be useful to know that they are also called vertices(sin. vertex ). They could represent anything: people, cities, almost anything you want them to.
Edges on the other hand represent connections between two nodes. They are generally represented as a unique pair(u, v) where u and v refer to the nodes on either end of the edge. This pair is usually ordered as it could cause problems if not ordered in a directed graph.
Now that we know somethings about nodes and edges, let’s move on to some commonly used terms in graphs. Basic knowledge of terminology helps you understand explanations of algorithms and code online with the added bonus of letting you flex on non-coding friends.
Some more about nodes…..
Adjacent nodes: Nodes that are connected directly to each other with the help of an edge are called Adjacent nodes.
Degree of a node: In undirected graphs, the number of nodes adjacent to a particular node u is called the degree of the node u. However, in directed graphs, the indegree is the number of edges arriving at the node and the outdegree is the number of edges departing from the node. If the degree of the node is 0, then the node is an isolated node as it isn’t connected to any other nodes. If the degree of the node is 1, then the node is a pendent node.
Some more about edges…..
Weighted edges: Edges carrying assigned values are called weighted edges. They are generally used to signify importance, width, cost etc.
Unweighted edges: Edges not carrying any specified values are called unweighted edges. The default weight taken is 1.
Directed edges: Edges with a specified direction in the form of a starting node and ending node are called directed edges. They are represented as an ordered pair(u, v) where u is the starting node and v is the ending node. An ordered pair(v, u) would represent a different edge in the opposite direction.
Types of graphs
Directed graphs: Graphs in which the direction of edges is specified are directed graphs. The following are types of directed graphs.
- DAG(Directed Acyclic Graph): It is a directed graph containing no cycles, i.e. there is no node u starting from which we follow the path of the graph and end up at u again.
- Trees: Trees are DAGs with the added condition that each node can have at most one parent node, i.e. the maximum indegree of any node is one.
Undirected graphs: Graphs in which the direction of edges is not specified. The following are types of undirected graphs.
- Connected graph: It is a graph where it is possible to reach any node from any other node. This means that every node is connected to at least one other node.
- Complete graph: It is a graph where each node is connected to every other node in the graph.