What is graph theory?

It is that part of network analysis where the configuration is called graph or structure of the network system when all of the elements (e.g., R, L, and C) in a network system are substituted with lines having circles/rings or dots across both endpoints. The study of the solution of the networks and circuits with the help of graphs is known as graph theory. The objective is to know the mathematics behind the network analysis.

What is the objective of graph theory?

The objective of graph theory is that all locations of the intersection of two or more parts (known as nodes or vertex) are kept in the network graph, and network elements are represented by lines, voltage, and current sources by their internal impedances. A directed graph or oriented graph is a structure that has directions or orientations for each branch.

Types of graph theory

There are different types of graph theory that are described in the detail below:

Directed and undirected graph

Any system is labeled as an undirected graph in the graph theory if its branches have no directions and a directed graph if the graph's branches have directions. A limited graph is used to be represented by an adjacency matrix.

Planar and non-planar Graph

In graph theory, if a graph could be constructed on a plane surface without any two branches crossing each other, that is because it is planar. A non-planar network in graph theory will have branches that are not in the same plane as others, implying that a non-planar figure or graph cannot be represented on a plane or level surface without a crossover.

Elements in graph theory

There are various elements of the graph theory that are discussed in detail below:

Subgraph

By definition, the number of vertex and edges in a subgraph is less or equal to the number number of vertex and edges in the entire graph. A sub graph's nodes (or vertex) and edges are defined to be always a subgroup of the graph's other nodes (or vertex) and edges. If a subset has fewer other nodes (or vertex) and branches than the original graph-theoretic, it is considered to be appropriate.

Path

By definition, it is defined as a subgraph consisting of an ordered sequence of branches with the feature that all internal nodes (or vertex) have exactly two subgraph branches. Only one branch is incident at each of the two terminal nodes (or vertex).

One important parameter of regulatory networks is the path length. The path length is defined as the total edges of the given graph.

Connected graph

 By definition, if there is a minimum single pathway connecting any two vertices (nodes) of a graph, it is defined to be a linked or connected graph. Unconnected graphs, on the other contrast, are those that comprise at least two distinct components.

Loop

By definition, it is defined as a representation of a graph wherein every node (or vertex) contains absolutely two branches. When specifying a loop, a group of nodes (or vertex) or branches that make up the loop must be stated; for example, a loop with nodes 1, 3, and 4 can be defined with branches (c, d, and f).

In graph theory, a loop in a graph has these properties:

• A loop should have at least two branches.
• The sum number of output nodes (or vertex) equals the sum number of branches.
• Any pair of nodes (or vertex) in the loop has exactly two pathways between them.

Tree and co-tree

In graph theory, a tree is a section of a directed structure or graph that contains all nodes but does not have any closed paths.

Properties of a tree:

• It is made up of all graph nodes.
• A tree branch contains (n-1) branches for an n-node graph.
• In a tree, there can't be any closed paths.

Twig

In graph theory, a twig is a name for a tree branch. A thick line is used to indicate a twig.

Co-tree

In graph theory, co-tree refers to the portion of a directed graph that is not covered by the tree. A dotted configuration represents a co-tree.

Link or chord

In graph theory, a dotted line represents the branch of a co-tree, which is known as a link or chord.

Incidence matrix

Analytically, in graph theory, an oriented graph can be represented by naming all branches and nodes and specifying how the branches are connected to each node. This can be done using a matrix called the incidence matrix, which is depicted by the letter A.

Properties of an incidence matrix:

• The nodes of the branch to which it is joined are identified by the unit entry in the column.
• A row of unit entries identifies the branches that occur at a node.
• A matrix's rank can't be higher than (n-1).
• If a node has a degree of two, it indicates that the two branches intersect at the node and are in series.

Common Mistakes

Remember that the sum of the set of twigs and connections in a directed graph equals the set of branches.

Also, remember that brain networks are the study of brain neurons. Brain networks are very complex networks. These complex networks can be studied with the help of clustering algorithms using the clustering coefficient. Clustering algorithms use clustering coefficients to group the brain networks and automatically reach the solution. Only inputs are fed to the system.

A scale-free network is a type of graph which follows a power law. Power laws possess the same formation at all scales, thus called scale-free.

Context and Applications

In each of the expert exams for undergraduate and graduate publications, this topic is huge and is mainly used for

• Bachelor of Technology in Electrical and Electronics Engineering
• Bachelor of Science in Physics
• Master of Science in Physics

Related Concepts

• Network topology
• NP-complete
• Springer-Verlag weighted graph

Practice Problems

Q1  A graph is a collection of points that is referred to as _______.

(a) nodes

(b) fields

(c) lines

(d) edges

Correct option- (a)

Explanation- A graph is a group of nodes or vertices that are connected by a network of lines called edges.

Q2 A graph is made up of _______.

(a) a set of vertices that isn't empty

(b) a set of vertices that is devoid of any vertices

(c) Both a and b are true.

(d) None of the preceding

Correct option- (a)

Explanation- A graph is made up of a collection of non-empty vertex or nodes V and a set of edges E.

Q3 What is the name of the number of connections or edges that intersect with the vertex V?

(a) A graph's degree

(b) Handshaking lemma 

(c) Vertex degree 

(d) None of the preceding

Correct option- (c)

Explanation- A vertex's degree is the number of edges attached with a source vertex of a directed graph G is indeed the degree of vertex V.

Q4 The clique number of triangle-free graphs is _________.

(a) more than ten

(b) less than five

(c) the same as five

(d) more than three

Correct option- (a)

Explanation- No three vertices can create a triangle of edges in an undirected triangle-free graph. Graph G with a clique value below two and girth more than four can be described like this.

Q5  What is the name of the graph/tree wherein every side/edge of the graph has a closed trail?

(a) Hamiltonian graphs

(b) Graphs of Euler

(c) Planar graph

(d) Directed graph

Correct option- (b)

Explanation- An Euler graph is a linked graph with a closed trail containing every one of the graph's sides.