Graphs Flashcards
Multigraph with loops
A graph where multiple edges between the same pair of vertices are allowed, and vertices can have loops
Simple graph with loops
A simple graph that allows loops (edges connecting a vertex to itself) but has at most one edge between any pair of distinct vertices
Simple graph without loops
A graph with no loops and at most one edge between each pair of vertices
Complete graph K_n
A simple graph without loops where every distinct vertex is connected with other vertices
n x (n-1) / 2 edges
Cycle Graph C_n
A simple graph without loops in which each vertex connects to exactly two distinct vertices, forming a closed loop
Bipartite graph
A simple graph without loops whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set(V_1) to vertex in the other set (V_2)
E ⊆ {{x_1, x_2} | x_1 ∈ V_1, x_2 ∈ V_2}
Complete bipartite graph K_m,n
A bipartite graph where each vertex in one set is connected to every vertex in the other set, with m * n edges
Directed multigraph with loops
Consists of a set of vertices, a set of directed edges (arrows) and two function that assign a source vertex and a target vertex to each arrow, allowing multiple arrows between the same vertices and including loops
Adjacent vertices
Two vertices that are connected by an edge in an undirected graph
How to calculate the degree of a vertex
The degree is the total number of edges connected to the vertex, with loops counted twice
Degree-Sum formula
∑v∈V deg(v)=2∣E∣, where each edge contributes twice to the sum of degrees
A walk in graph theory
A sequence of edges connecting a sequence of vertices in a graph
A circuit in a graph
A closed walk where the start and end vertices are the same
Euler circuit
A circuit that uses each edge of the graph exactly once
A path
A walk where no vertices are repeated
