Graph Theory Flashcards
is a mathematical structure that consists of a set of nodes (or vertices) and a set of edges that connect pairs of nodes.
Graph
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
These are the fundamental elements of a graph.
They represent individual entities, points, or objects.
Nodes (Vertices)
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
The graph that has no edges is sometimes called
Null graph
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 that does not contain parallel edges or loops.
Simple graph
Is a sequence of vertices and edges of a graph.
Edge and Vertices both can be repeated.
Walk
The starting and ending vertices in this walk are different
Open walk
The starting and ending vertices in this walk are identical
Close walk
An open walk in which no edge is repeated.
Vertex can be repeated.
Trail
A graph is considered this 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
Path
A graph where we do not repeat a vertex nor we repeat a edge but the starting and ending vertex must be the same
Cycle
If at least two vertices of the graph are not connected by a path then the graph is
Disconnected Graph
In this graph, edges have a direction, indicating that a relationship between nodes is one-way.
Directed Graph (digraph)
In this graph edges have no direction, meaning the relationship between nodes is mutual.
Undirected Graph
