Terminologies Flashcards
Size of Graph
Cardinality of Edge set
Order of Graph
Cardinality of Vertex Set
Adjacent Edges
Two edges are adjacent if they have are incident on a common vertex
Subgraph
H is a subgraph of G if
V(H) is a subset of V(G)
and E(H) is a subset of E(G)
Improper Subgraph
Every graph is a subgraph of itself, and since it is equal, it is an improper subgraph
Proper Subgraph
A graph H that is a subgraph of graph G, and H!=G is called a proper subgraph
Spanning Subgraph
A subgraph H is a spanning subgraph of G is if V(H)=V(G) and E(H) is a subset of E(G)
Vertex induced subgraph
a subgraph of a given graph that contains a subset of the vertices of the original graph and all the edges that are present between those vertices.
Edge induced subgraph
A subgraph of a given graph that contains a subset of the edges of the original graph and the vertices incident to those edges
Walk
A walk in a graph is a sequence of vertices where consecutive vertices in the sequence are adjacent.
A walk can repeat vertices and edges
Path
If a walk does not repeat any edges and vertices, it’s called a path.
Trail
A walk in which you cannot repeat edges.
Closed Walk, Path or Trail
If a walk, path or trail that starts and ends at same vertex is a closed walk/path/trail
Circuit
A closed trail
Cycle or simple cycle
A cycle, often referred to as a simple cycle, is a closed path where no vertex (except for the starting and ending vertex) and no edge are repeated.
Connected Vertices
Vertices within a graph that are connected to each other by some path
Component of a graph
A component of a graph is a maximal subgraph in which every pair of vertices is connected by a path, and which is not connected to any additional vertices outside of the subgraph.
Distance between two vertices
Length of the shortest path between two vertices.
Geodesic
Shortest path between two vertices in the graph
Diameter
Largest distance in a graph
