Graphs Flashcards
(19 cards)
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
Path
A walk where no vertices are repeated
Cycle
A path that starts and end at the same vertices
Subgraph
A graph derived from another graph by deleting some edges or vertices
Circuit
A cycle but vertices can be repeated
