graph Flashcards
is a city on the Pregel river in Prussia
- The city occupied two islands plus areas on both banks
Kรถnigsber Bridge Problem
the greatest mathematician
that Switzerland has ever
produced
LEONHARD EULER
A branch of mathematics concerning with network of
points connected by lines (Carlson, 2020).
โข It is ultimately the study of relationships (Flovik, 2020).
mathematics of graph
: a region
A vertex
: a path(bridge) between two regions
An edge
A relation between an edge and a pair of vertices
graph
The number of vertices in G, ๐ฃ(๐บ)
order
The number of edges in G, ๐(๐บ)
size
๐ฝ(๐ฎ )
vertex set
๐ฌ(๐ฎ )
edge set
An edge whose endpoints are equal
loop
Edges have the same pair of endpoints
multiple edges
A graph has no loops or multiple edges
Simple graph
Two vertices are ___ and are ___if they are
the endpoints of an edge
adjacent, neighbors
a graph whose vertex set and edge set are
finite
finite graph
the graph whose vertex set and edges are
empty
null graph
the edges form
the same connections of vertices in each graph.
equivalent graphs
A simple graph
โข ๐(๐บโ) = ๐(๐บ)
โข ๐ธ(๐บโ) = { ๐ข๐ฃ | ๐ข๐ฃ ๏๐ธ(๐บ) }
complement
a set of pairwise adjacent vertices (a
complete subgraph)
Clique in a graph
a set of pairwise
nonadjacent vertices
independent set in a graph
if ๐ฝ(๐ฎ) is the union of two disjoint
independent sets called partite sets of ๐ฎ
- The vertices can be partitioned into two sets such
that each set is independent
bipartite graphs
the
minimum number of colors needed to label the vertices
so that adjacent vertices receive different colors
- X(G) = 3
chromatic number
a partition of the plane into connected regions
map
Two committees can not hold meetings at the same time
if two committees have common member
SCHEDULING AND
GRAPH COLORING
a sequence of distinct vertices such that two
consecutive vertices are adjacent
path
a closed Path
cycle
The assignment of endpoints to edges in H is the
same as in G
subgraph
There exists at least one path between two
vertices
connected
there is no path between two vertices
disconnected
The vertices vj and vk
adjacent
The edge ei
is said to be ___upon vj
incident
vertex vk
is the number of edges incident
upon vk
. It is denoted as d(vk)
Degree
the n-by-n
matrix in which entry ai,j is the number of edges in G
with endpoints {vi
, vj}
adjacency matrix
the n-by-m matrix in which
entry mi,j is 1 if vi
is an endpoint of ei and otherwise is 0
incidence matrix
a simple graph whose vertices are
pairwise adjacent
complete graph
is a simple bipartite
graph such that two vertices are adjacent if and only if
they are in different partite sets.
biclique or complete bipartite graph
list of vertices and edges v0
, e1
, v1
, โฆ., ek
, vk
such that, for 1 ๏ฃ i ๏ฃ k, the edge ei has endpoints vi-1 and
vi .
walk
a walk with no repeated edge.
trail
graph with vertex degrees all even.
EVEN GRAPH
vertex is odd [even] when its degree is odd?
odd graph/ odd vertex
graph that can be drawn without any breaks in the
curve without repeating any edge.
โข A graph with more than two odd vertices is NOT
traversable.
TRAVERSABLE GRAPH
it has a closed traversable trail.
โข Theorem: A graph G is Eulerian if and only if each vertex
has an even degree
Eulerian Graph
A graph with a closed path that passes through all
vertices exactly once.
HAMILTONIAN GRAPH
when we do not specify the
first vertex but keep the list in cyclic order.
circuit
graph is a circuit
or trail containing all the edges.
Eulerian circuit or Eulerian trail
circuit that uses every edge, but never uses the same
edge twice, is called an
euler circuits
a path that uses
every edge once and only once
euler path
This path visits each vertex once and returns to the
starting vertex without visiting any vertex twice.
Hamiltonian circuit.
Consider a connected graph with at least three vertices
and no multiple edges. Let ๐ be the number of vertices in
the graph. If every vertex has degree of at least ๐
2
, then
the graph must be Hamiltonian.
diracโs theorem
is so called because it
has us choose the โcheapestโ option at every
chance we get
greedy algorithm
Use the ____ to find a Hamiltonian
circuit
edge-picking algorithm
