Content Curator
Drawing graph is a method of representing the textual data on a graph paper. Usually, two sets of values are evaluated and some relation is figured out between them. But a graph can represent subsets of the given data as well, making comparison an easy process. The main two components are nodes and vertices. Nodes are dots or points whereas vertices are lines that join these dots to complete the graph. Graphs should not be confined to mathematics, but its application can be extensively seen in Physics, Chemistry, Computer Science and a whole lot of scientific research.
Read More: Concepts in Probability and Statistics
| Table of Content |
Key Takeaways: Graph Theory, Plotting, Data, Edges, Vertices & Dots
What is Graph Theory?
[Click Here for Sample Questions]
Graph is the pictorial representation of tabular data. The data is plotted on the graph using the Vertices (V) or dots and Edges (E) or lines. Graph Theory explains the use of graphs in discrete mathematics rather than on continuous data. Using V and E, a graph is expressed as G(V,E).
The graph theory is most accurate and widely used for discrete variables due to its distinct nature. In continuous variables sometimes graph theory results are true but of no use. For example, the number of cars sold is 1.5, which makes no sense.
Edges, Nodes and Vertices
Also Read:
| Related Articles | ||
|---|---|---|
| Graphs of Linear Equation | Parabola | |
| V-T Graphs | Graphs of Inverse Trigonometric Functions | |
| Median | Frequency Distribution Table | |
| Mean of Grouped Data | Graphical Representation of Data | |
History of Graph Theory
[Click Here for Sample Questions]
The inception of the graph occurred in the 18th century when the Swiss Mathematician Leonhard Euler was asked about the layout of the German town, Konigsberg. Konigsberg is situated on the Pregolya river and a total of four land bodies including Konigsberg are present on the map. Each of the land bodies are connected to each other by a total of 7 bridges.
History of Graph Theory
Once Leonhard Euler was asked to show a path by which one can travel throughout the city by crossing the seven bridges only once. This path is also known as the Euler Path. In the process, he plotted the first ever graph with vertices and edges.
Euler’s Path
After research he came to the conclusion that the Euler path is possible for a graph with zero or two odd numbers of nodes.
Different Types of Graph
[Click Here for Sample Questions]
The graph which Euler devised is not much in use today. Many modifications have led to various types of graph and each useful in its own way. On the basis of direction, it is divided into two:
Undirected Graph
Undirected graph is a graph where there is no defined direction of the edges. It is also known as a non-networked or no-network graph.
Directed and Undirected Graphs
Directed Graph
Directed graphs have well-defined directions as arrows drawn on edges.
Properties of Graph
[Click Here for Sample Questions]
- The starting point of the node is known as root.
- A graph with a single cycle is known as a cycle graph.
- A complete graph is the one in which no node is left open.
- Graphs may differ on the type of nodes connected to each other. When similar nodes are connected it is an assortative graph or otherwise known as a disassortative graph.
Important Terms of Graph
[Click Here for Sample Questions]
Tree: Tree is a type of undirected graph where any two nodes or vertices are connected only with one edge. It looks like the prototype of a tree or spider web.
Degree: Degree of a graph is the counting of edges connected to a vertex. In an undirected graph the degree can simply be found by counting the number of edges going in and out of a vertex. But in a directed graph there are two types of degrees, Indegree which is the number of edges coming in a vertex and Outdegree is the number of edges going out of a vertex.
Degree of graph
Cycle: When a few vertices and nodes in a graph become a loop, it is called a cycle. A cycle may be further classified as odd and even, depending on the number of edges and vertices in the cycle. Odd cycle has odd no. of edges or vertices and vice-versa.
Uses of Graph Theory
[Click Here for Sample Questions]
- The best example of application of graph theory is to find the minimum distance between two locations. Google maps is an example of graph theory where the destination and stops in between can be considered as nodes and the path as vertices.
- In physics and chemistry graph theory is used to study the atomic structure of elements. The atoms in a connected graph on a 3-D plane are easier to understand than in 2-D form.
- The connectivity among computers like LAN, MAN, WAN resembles graph theory.
Things To Remember
- The graph theory will be more useful on discrete and finite data. Using continuous data will be hectic and may give inaccurate results.
- Graph theory must not be confused with graphs in statistics. They are graphical representations of the recorded data on graph paper whereas graph theory is about connecting dots to form a network.
- Graph theory is to find the minimum distance between two locations.
- Based on the direction, Graphs can be divided into Directed graphs and Undirected graphs.
Also Read:
Sample Questions
Ques. Draw a Complete Graph and calculate the number of vertices and edges. (2 Marks)
Ans.
The complete graph given below has 5 vertices and 10 edges. The formula to find the number of edges is n(n-1)/2 where n is the number of vertices.
Here, n = 5
⇒ (5 * 4)/2 = 10.
Ques. What is a connected graph? Give a diagram of a connected graph. (2 Marks)
Ans. A connected graph is one where all the nodes are connected to some other node/ There is no node that cannot be reached with a path. An example of a connected graph is given as:
Ques. What is the Indegree in a graph. Calculate the Indegree of the vertex 4 in the graph given below. (2 Marks)
Ans. Indegree is the number of edges coming at and arriving at a point. In vertex 4, a total of 2 edges are coming in. Hence, the Indegree of vertex 4 is 2.
Ques. Suppose there are a total of 25 schools in a large area. And each school is connected to only 4 other schools. Calculate the total number of roads or paths connected to all of them. (3 Marks)
Ans. Using graph theory we can consider 25 schools as 25 points or vertices. The degree of each vertex is 4. The road or path connecting schools can be considered as an edge.
From the given data we can calculate the sum total degree of all vertices i..e 25 *4 =100
We know that,
Sum of all degrees of each vertex = 2 * (number of edges)
⇒ 100 = 2 * (number of edges)
⇒ number of edges = 100/2 = 50.
Therefore, the total roads connecting schools is 50.
Ques. There are 11 line segments drawn on a piece of paper. Is it possible that each line segment is exactly connected to 3 others? If yes, then find the sum of degrees of all vertices. (2 Marks)
Ans. Given there are a total of 11 line segments, which means a total of 11 vertices. The degree of each vertex is 3 and the total degree is 3 * 11 = 33 .
The number of edges can be found from the formula:
Sum of all degrees of each vertex = 2 * (number of edges)
⇒ 33 = 2 * (number of edges)
⇒ 33/2 = (number of edges)
⇒ number of edges = 33/2 = 16.5
As the number of edges cannot be in decimals, hence, this graph is not possible.
Ques. Give one real life example of Graph Theory. (2 Marks)
Ans. The Internet which we use everyday for browsing the web, downloading and uploading information is a large web of computers and servers. This web of networks works on the principle of graph theory where each serve can be considered as a vertex and edges are the wires or wireless connections.
Given below is a diagram of the Internet and its connections.
Ques. What is the Euler Path and Euler Circuit? Explain it with a diagram. (2 Marks)
Ans. The Euler Path is a graph where each point comes once only. No node or vertex is repeated in the path. A Euler Circuit is a circuit where all the vertices have an even degree.
In G1 the path starts from a and goes like a,c,d,a,b,d. The degree of a and d is odd so hence, it is a Euler Path but not Euler Circuit.
In G2, the degree of all vertices is even, so it is an Euler Circuit.
Ques. What is a root in a tree? Draw a tree and show its root. (2 Marks)
Ans. The starting point of a node or vertex is known as its root. A tree is a subcategory of an undirected graph where every node has a degree of one, i.e., it is connected to only one other vertex.
For Latest Updates on Upcoming Board Exams, Click Here: https://t.me/class_10_12_board_updates
Check-Out:
Comments