Graph Theory Flashcards
is a branch of mathematics and computer science that deals with the study of graphs
Graph theory
SIGNIFICANCE OF GRAPH THEORY
Mathematical Abstraction
Networks
Transportation and Routing
Social Sciences
Computer Science
Circuit Design
is a mathematical structure that consists of a set of nodes (or vertices) and a set of edges that connect pairs of nodes.
Graph
These are the fundamental elements of a graph, it represent individual entities, points, or objects.
Nodes (Vertices))
These are connections between pairs of nodes. They represent relationships, interactions, or links between the corresponding entities.
Edges
The number of vertices of a graph.
Order
If there is more than one edge that connects two different vertices.
Parallel Edges
An edge that connects a vertex to itself.
Loop
A graph does not contain parallel edges or loops.
Simple graph
a sequence of vertices and edges of a graph i.e. if we traverse a graph . Edge and Vertices both can be repeated.
Walk
if the starting and ending vertices are different i.e. the origin vertex and terminal vertex are different.
Open walk
if the starting and ending vertices are identical i.e. if a walk starts and ends at the same vertex.
Closed walk
is an open walk in which no edge is repeated. Vertex can be repeated.
Trail
If there is a path between any pair of nodes. In other words, no nodes are isolated.
Connected Graph
It is a trail in which neither vertices nor edges are repeated i.e. if we traverse a graph such that we do not repeat a vertex and nor we repeat an edge. It is also an open walk
Path
