20240311: Graphs Flashcards
Learn the notations and definitions from the first part of the lecture.
Graph
Definition
Unidrected Graph
A graph G is an ordered pair (V, E) consisting of a set of vertices and a set of edges, disjoint from V, together with an incidence function Ψ that associates with each edge an unoredered pair of not necessarily distinct vertices in V.
Order and size of a graph G
Terminology; notation
Undirected Graph
- Order: the number of vertices in graph G (denoted by n or v(G))
- Size: the number of edges in graph G (denoted by m or e(G))
True or false:
Adjacency happens between an edge and a vertex.
False.
Adjacency happens between two edges (sharing a vertex) or between two vertices (sharing an edge).
True or false:
Incidence happens between two vertices or two edges.
False.
Incidence happens between an edge and its ends, or between a vertex and its edges.
Neighbours of a vertex v
Terminology; notation
Undirected Graph
N_G(v): a set of neighbours of a vertex v in graph G.
Loop; parallel edge
Terminology
Loop: an edge with identical ends.
Parallel edge: multiple edges with the same ends.
Finite graph; null graph; trivial graph; simple graph
Terminology
- Finite graph: has finite sets of vertices and edges
- Null graph: no vertices
- Trivial graph: only one vertex
- Simple graph: no loops or parallel edges
Complete graph; empty graph; bipartite graph
Terminology
- Complete graph: simple graph in which any two vertices are adjacent
- Empty graph: an empty edge set
- Bipartite graph: vertex set split in two, each edge connects a vertex from one part with a vertex in the other
True or false:
A graph is complete bipartite if it is simple and every vertex from one part is connected to every vertex in the other part.
True. Example: Star, S_n
Complete graph
Notation; characteristics
Complete graph: denoted by K_n
- number of vertices: n; number of edges: n over 2
Bipartite graph
Notation; characteristics
- Bipartition denoted by (X, Y)
- Bipartite graph denoted by G[X, Y]
- Number of edges: 2^n
Path
Terminology; notation
A simple graph whose vertices are arranged in a linear sequence so that two vertices are adjacent if they are consecutive in the sequence, and not otherwise.
- denoted by P_n
- number of vertices: n; number of edges: n-1 -> length
Cycle
Terminology; notation
A simple graph on two or more vertices that can be arranged in a cyclic sequence, so that the rule for the path holds.
- denoted by C_n
- number of vertices/edges: n -> length
True or false:
In a path or a cycle, parity is determined by the length.
True. The number of edges being odd or even determines the parity of the path or a cycle.
When is a graph (dis)connected?
- Not connected: if the vertex set can be split in two parts such that there are no edges connecting vertices in different parts. Otherwise, connected.
True or false:
Is every connected graph bipartite?
False. Every bipartite graph is connected, by the definition of connectedness. It does not hold in the other direction.
Vertex degree
Terminology; notation
Undirected Graph
Vertex degree: number of neighbours (adjacent vertices); denoted by d(v)
- isolated vertex: d(v) = 0
- minimum degree: min. value of degrees in a graph; denoted by δ(G)
- maximum degree: max. value of degrees in a graph; denoted by Δ(G)
- average degree: d(G) = 1/2 sum d(v), sum over v in V
True or false:
Every vertex degree of a regular graph is the same.
True. It is also called a k-regular graph, for some k = d(v), for all vertices.
Isomorphism
Definition
Two graphs G and H are isomorphic if there is a bijection Θ: V(G) -> V(H), such that uv in E <=> Θ(u)Θ(v). They have the same n, m and degree sequence.
True or false:
An unlabelled graph is a representative of an equivalence class of isomorphic graphs.
True
Line graph
Definition; notation
A representation of G where the vertex set of a line graph is the edge set of G, and two edges are adjacent if they have an end in common; denoted by L(G).
