Discrete Mathematics - Graphs Flashcards
What is a Graph
A diagram of vertices connected by edges
What is a vertex
A point on a graph where edges meet and intersect
What is an edge
A line connected to a vertex
What is an Isomorphic Graph
A graph that display the same set of veritces and edges as another graph
What is a connected graph
A graph by which you can travel from one vertex to any other vertex on the graph
What are multiple edges
Two or more egdes that connect to the same pair of vertices
What is a loop
A vertex connected to itself by the same edge
What is meant by the degree of a vertex
The number of edges that a vertex is incedent ( connected ) to
What is a Simple graph
A graph that has no multiple edges or loops
What is a Sub-graph
A graph formed by some of the vertices and edges of the original graph
What is a Planar Graph
A graph that has no edges that cross over each other
What is a Bipartite graph
A graph containing 2 distinct sets of vertices that have edges which connect vertices from one set to another
How is a Bipartite Graph denoted
Kₙ,ₘ where ₙ is the number of vertices in the 1st set and, ₘ is the number of vertices in the 2nd set.
What is a Complete Graph
A simple graph where each vertex is connected to all other vertices within the graph by an edge
How is a Complete graph denoted
Kₙ where ₙ is the number of vertices in the graph.
What is a subdivision
Where a vertex has been added to an edge, between a direct pair of vertices
What is the equation relating the number of degrees and edges within a graph
Degrees (D) = 2 x Edges (E)
What is a Euler’s Formula
V + F - E =2
What is a face in a graph
Areas created by edges drawn on a plane
What is an adjacency matrix
A table showing for a graph, the vertices and the number of edge connections between them, and for networks, thee nodes and the weighted connections between them on one arc
How is a Complement Graph denoted
G’
What is a trail
A sequence of vertices and edges with no repeated edges
What is a Cycle
A sequence of vertices and edges that starts and finishes on the same vertex, and have no repeated edges or vertices
Explain why Kₙ,ₘ has mn edges
Each vertex in the first set is connected by an edge to each vertex in the other set. Meaning that there are n edges for every m vertices
Where is an adjacency matrix symetrical from
The lead diagonal
What is meant by the complement of a simple graph
A set of edges such that when added to the original graph gives a complete graph
What is a tree
A simple connected graph with no cycles
What is the trend for the degrees of vertices in a tree / tree branch
The vertices at the end of the branch have a degree of 1. This means a tree with n vertices must have a minimum of 2 vertices with degree 1 and a maximum of n - 1 vertices of degree 1.
What is a Traversable graph
A graph that can be drawn as a trail without going ove the same edge twice
What is an Eulerian Graph
A graph that has no vertices with an odd degree
What is a Semi-Eulerian Graph
A graph that has exactly 2 vertices with an odd degree
What is a Hamiltonian Graph
A graph that contains a cycle that passes through each vertex once, and starts and ends on the same vertex
