Graphs Flashcards
Vertices
Is the points
Edges
Is the line connecting to the points
Degrees
Number of edges connected to that vertex (loops are double counted)
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
A simple graph without loops where every distinct vertex is connected with other vertices
n x (n-1) / 2 edges
Cycle graph
A simple graph without loops in which each vertex connects to exactly two distinct vertices, forming a closed loop
has n edges
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
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
Degree-Sum formula
Number of degrees = 2 * edges
(Sum of degrees of all vertices = 2 * number of edges)
Walk
A walk allows traversal through any sequence of edges, and both vertices and edges can be revisited multiple times.
Euler circuit
Is a circuit which uses each edge of the graph precisely once
