After Midterm Flashcards
Simple Graph
A simple graph G =(V,E) consists of a non-empty set of Vertices V and a set E of unordered pairs of distinct elements of V called edges
Multigraph
When a graph allows multiple edges between pairs of vertices, we call it a multigraph.
Pseudograph
A multigraph that allows for loops
Directed Graph
A directed graph G = (V,E) that consists of a non-empty set of vertices V and a set E of ordered pairs of distinct elements of V called edges.
Order
of vertices (Typically n)
Size
of edges (Typically m)
Max # edges for simple graph
n choose 2 = (n(n-1))/2
Max # edges for direct graph
n^2
Same degree theory
In a simple graph of n>1 vertices, there is always two vertices with the same degree
(u,v) in an edge in a directed graph
u is adjacent to v
v is adjacent from u
Handshaking Theorm
If you divide the sum of the degrees of a simple graph by 2 you get the number of edges
Bipartite Graph
A simple graph is bipartite if the set vertices V can be split into two sets V1 and V2 such that all edges have one endpoint in V1 and one in V2.
Matching
A matching is a subset of edges such that no two edges are incident with the same vertex
Maximum Matching
A matching with the largest amount of edges possible
Subgraph
A subgraph of G = (V, E) is a graph G = (W,F) such that W is a subset of V and F is a subset of E.
Induced Subgraph
An induced subgraph has the same properties as a subgraph, although additionally, all edges between two vertices in the subgraph must be present if they are in the original.
Isomorphism
Two simple graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if there is a one-to-one and onto function from V1 to V2 such that edge (u,v) is in E1, if and only if (f(u),f(v)) is in E2 for all edges.
Path
A path is a sequence of vertices V0,V1…Vn where there is an edge between each consecutive pair of vertices
Simple Path
A path that doesn’t contain the same vertex more than once
Cut Vertex
A vertex is a cut vertex if the removal of it and its incident edges leaves the graph disconnected
Vertex Cut
A subset V1 of V such that G-V1 is disconnected
Directed Graph: Strongly Connected
There is a path from (u,v) and (v,u) for every pair of vertices.
Directed Graph: Weakly Connected
The graph is connected when direction is removed
Euler Path
A path that traverses every edge exactly once in an undirected graph (Two vertexs of odd degree)
Euler Cycle
A cycle that traverses every edge exactly once (Starts and ends at the same vertex)
(All vertexs of even degree)
Hamilton Path
A path that visits every vertex exactly once
Hamilton Cycle
A cycle that visits every vertex exactly once (Except the first and last…. starts and ends at the same vertex).
Hamiltonian
If a graph contains a Hamilton cycle it is hamiltonian
Dirac’s Theorem
If G is a simple graph with n>2 vertices such that each vertex is at least n/2, then G is Hamiltonian.
Ore’s Theorem
If G is a simple graph with n>2 vertices such that deg(u) +deg(v) >= n for every pair of non-adjacent vertices u and v, then H is hamiltionian
Planar
A graph is planar if it can be drawn on a plane without any edges crossing
Euler’s Formula
If G is a connected planar simple graph with n vertices and m edges and if r is the # of regions in the planar representation of G, then r = m-n+2
Properties of planar graphs: Corollary 1
If G is a connected planar simple graph, with n>=3 vertices and m edges, then m <=3n-6
Properties of planar graphs: Corollary 2
If G is a connected planar simple graph, then G has a vertex with degree <=5
Homeomorphic
Two graphs are homeomorphic if they can be obtained from the same graph by a sequence of subdivisions.
Kuratowski’s Theorem
A graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3
Four Colour Theorem
A planar graph or map has a chromatic # of 4 or less
Spanning Tree
A subgraph of a connected simple graph G that is a tree containing every vertex of G
Minimum Spanning Tree (MST)
When edges are weighted, MST of G is the spanning tree where total weight (sum of weights of its edges) is the minimum possible.
*If all edge weights are unique, then there is a unique MST
