Mathematics Discrete Mathematics Graph Theory | Basic Terminology | Discrete Math |...

Graph Theory | Basic Terminology | Discrete Math | CS School


Graph is all about dots and lines connecting them. Or we can simply say that a Graph is a collection of vertices (also called nodes) and edges (connections between nodes). So when talking about Graph Theory, it is just points and lines connecting them. Now, let’s begin with more formal discussion on Graph Theory.

Graph Theory | Basic Terminology 

definition of Graph: A graph G is a non empty finite set of vertices V along with a set of edges E (also incidents between vertices) of unordered pair of distinct vertices, or subsets of V. So we can say a GraphG = <V, E>.

Graph Theory | Graph Terminology - cs school

Figure: Graph Theory | Graph Terminology
[g here isolated vertex]

Terminology: Here, we can see in above figure that points indicate vertices (a, b, ..), and lines that join vertices are edges. From the definition we have learned that edges are unordered pairs of vertices. Therefore it is common to denote an edge consisting vertices. Such as, we can denote edge $E_{1}$ consisting vertices a, b. So, $E_{1}$= {a, b}, which is a subset of vertices V = {a, b, c, d, e, f}. In graph theory, the notion of {b, a} denotes the same edge as {a, b} for undirected graph. Any edge $E_{1}$= {ab} in graph theory, the vertices a, and b are the ends of the edge  $E_{1}$. Therefore,

Incident: $E_{1}$ is an incident to both a, and b.
Adjacent: a is adjacent to vertices b, e, and f. e adjacent to a. We often call adjacent vertices neighbour. 
Degree of Vertex: For any vertex a, the degree of a denoted deg(a), is the number of edges incident to it. 
Even or Odd: A vertex is even, or odd if its degree is even or odd.
Isolated vertex: A vertex of degree zero, means no edges or incident refers to as isolated vertex.

Types of Graph

There are two types of graph: Undirected, and Directed. In undirected graph edge $E_{1}$= {a, b}, same as writing {b, a}. Because in undirected graph we do not consider direction, so order does not matter. But in directed graph order does matter. Therefore we label this as ordered pair. So, $E’_{1}$= <a, b>, that means we say, we have a tail coming from a and we have a head going to b. So, $E’_{1}$= (a → b).

Graph Traversing or walk Through the Graph | x-y walk

A walk in a graph is a sequence of vertices and edges. So, 
Walk W = x $e_{1}v_{1}e_{2}v_{2}e_{3} … v_{n-1}e_{n}$ y. Here, we start from x then we take some edge $e_{1}$, then get another vertex $v_{1}$ so on and so forth until we get to y.

Now from above Graph G the set of vertices V = {a, b, c, d, e, f, g}. The set of edges E = {{a, b}, {a, c}, {a, d}, {b,e}, {b, c}, {e, f}}. 

Cardinality of Graph: Cardinality of Graph represents the number of vertices. Absolute value of G |G| denotes the cardinality of the Graph. So, |G| = 7.  Degree of vertex a, deg (a) = 3. Because the number of edges coming out from a is 3. Adjacency list of the graph
a: b, c, d
b: a, c, e
c: a, b
d: a
e: b, f
f: e
g: isolated vertex

Adjacency Matrix: in graph theory, adjacency matrix is a matrix configuration that shows the connection of vertices between one another. This is the matrix form of above adjacency list of graph. Vertex that connected with other vertices we represent them in the matrix with 1. -and the vertex that has no edges between other vertices, we represent them with 0.

graph theory - adjacency matrix

There is also an idea of graph isomorphism, which is a graph of same number of vertices and same number of edges but connected different way. read here>>

//This is the end of general discussion on graph theory. Read more articles on Discrete Mathematics, here>>

Latest Articles

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

SVD | Singular Value Decomposition | Machine Learning Fundamentals

Singular Value Decomposition or SVD is the general purpose useful tool in Numerical Linear Algebra for data...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a...

You might also likeRELATED
Recommended to you