Simple Graph Theory Flashcards
a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices.
graph
A graph is a collection of points called _____________ and line segments or curves called _________that connect the vertices
vertices or nodes
edges
an edge connecting a vertex to itself.
loop
a graph that has an edge connecting every pair of vertices.
complete graph
Two vertices are _______ if there is an edge joining them.
adjacent
Graphs are considered as _______if they have same vertices connected in the same way.
equivalent
an alternating sequence of vertices and edges. It can be seen as a trip from one vertex to another using the edges of a graph.
path
If a path begins and ends with the same vertex, it is a closed path or a _______
circuit or cycle.
A graph is _________ if for any two vertices, there is at least one path that joins them.
connected
an edge that when you remove makes the graph disconnected.
bridge
a vertex is the number of edges attached to it.
degree
The diagram below appears in a book in psychology. It is used to indicate ”_________ ” which occur in man- woman relationships.
transactions
One of the subjects studied by mathematicians is _________. The idea is to color the vertices or edges of a graph in such a way that adjacent vertices or concurrent edges are given different colors.
graph coloring
The smallest number of colors required to color the vertices of a graph
chromatic number of the graph.
chromatic number of the graph.
Colorable Graph Theorem
A graph is 2-colorable if and only if it has no circuits that consist of odd number of vertices.
Colorable Graph Theorem.
The chromatic number of a planar graph is at most 4.
Four-Color Theorem
A map can be represented by a graph with the different regions as vertices. Two regions are _____ if they share part of their boundaries.
Map Coloring
adjacent
The graph representing a map is ____. Hence, it needs only 4 colors.
planar
- a path that passes through every edge exactly once only
- a path that contains all the edges of the graph
- begin and end with the odd-degree vertices
Euler path
A graph has an ______ if and only if no more than two of its vertices have odd degree.
Euler path
a graph is a closed path that contains all the edges of the graph.
Euler circuit
A graph that has an Euler circuit is called
Eulerian
Eulerian if and only if each vertex has even degree.
connected graph
a graph is a path passing through each vertex of the graph exactly once.
Hamiltonian path
If the path is closed, it is called
Hamiltonian cycle.
If a graph has a Hamiltonian cycle, it is called __________
Hamiltonian
Every ____________- with more than two vertices has a Hamiltonian circuit. Furthermore, the number of Hamiltonian circuits in a complete graph with n vertices is (n-1)!.
complete graph
the same if they pass through the same vertices in the same order, regardless of the vertex where they begin and end.
Two Hamiltonian circuits
a graph in which any two vertices are connected by exactly one path.
tree
an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees is known as forest. Each component of a forest is tree.
forest
a graph is a tree that results from the removal of as many edges as possible from the original graph without making it disconnected.
spanning tree
A _____________ for a weighted graph is the spanning tree for the graph that has the smallest possible sum of the weights.
minimum spanning tree
A ____________ must have one fewer edge than the number of vertices.
minimum spanning tree
a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which
Prim’s algorithm
A graph is ______ if it can be drawn in such a way that no edges cross. This means that any two edges can meet only at an endpoint.
planar
Four-Color Theorem. The chromatic number of a planar graph is __________.
4
used to depict ”what is in conflict with what”, and colors are used to denote the state of a vertex.
GRAPH COLORING
the theory of ”partitioning the sets having Internal unreconcilable conflicts.
coloring theory
Vertex Coloring: It is a way of coloring the vertices of a graph such that no two adjacent __________ share the same color.
vertices
An edge coloring assigns a color to each edge so that no two adjacent edges share the same color.
Edge Coloring
a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
face coloring
The chromatic number of a graph is the minimum number of colors in a proper coloring of that graph. If chromatic number is r then the graph is r-chromatic.
Chromatic Number
A _________ can be represented by a graph with the different regions as vertices. Two regions are adjacent if they share part of their boundaries.
map coloring
The graph representing a map is planar. Hence, it needs only _______ colors.
4
