graph Flashcards

1
Q

is a city on the Pregel river in Prussia
- The city occupied two islands plus areas on both banks

A

Kรถnigsber Bridge Problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

the greatest mathematician
that Switzerland has ever
produced

A

LEONHARD EULER

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

A branch of mathematics concerning with network of
points connected by lines (Carlson, 2020).
โ€ข It is ultimately the study of relationships (Flovik, 2020).

A

mathematics of graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

: a region

A

A vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

: a path(bridge) between two regions

A

An edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

A relation between an edge and a pair of vertices

A

graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

The number of vertices in G, ๐‘ฃ(๐บ)

A

order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

The number of edges in G, ๐‘’(๐บ)

A

size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

๐‘ฝ(๐‘ฎ )

A

vertex set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

๐‘ฌ(๐‘ฎ )

A

edge set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

An edge whose endpoints are equal

A

loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Edges have the same pair of endpoints

A

multiple edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

A graph has no loops or multiple edges

A

Simple graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Two vertices are ___ and are ___if they are
the endpoints of an edge

A

adjacent, neighbors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

a graph whose vertex set and edge set are
finite

A

finite graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

the graph whose vertex set and edges are
empty

A

null graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

the edges form
the same connections of vertices in each graph.

A

equivalent graphs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

A simple graph
โ€ข ๐‘‰(๐บโ€™) = ๐‘‰(๐บ)
โ€ข ๐ธ(๐บโ€™) = { ๐‘ข๐‘ฃ | ๐‘ข๐‘ฃ ๏ƒ๐ธ(๐บ) }

A

complement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

a set of pairwise adjacent vertices (a
complete subgraph)

A

Clique in a graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

a set of pairwise
nonadjacent vertices

A

independent set in a graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

bipartite graphs

22
Q

the
minimum number of colors needed to label the vertices
so that adjacent vertices receive different colors
- X(G) = 3

A

chromatic number

23
Q

a partition of the plane into connected regions

24
Q

Two committees can not hold meetings at the same time
if two committees have common member

A

SCHEDULING AND
GRAPH COLORING

25
a sequence of distinct vertices such that two consecutive vertices are adjacent
path
26
a closed Path
cycle
27
The assignment of endpoints to edges in H is the same as in G
subgraph
28
There exists at least one path between two vertices
connected
29
there is no path between two vertices
disconnected
30
The vertices vj and vk
adjacent
31
The edge ei is said to be ___upon vj
incident
32
vertex vk is the number of edges incident upon vk . It is denoted as d(vk)
Degree
33
the n-by-n matrix in which entry ai,j is the number of edges in G with endpoints {vi , vj}
adjacency matrix
34
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
35
a simple graph whose vertices are pairwise adjacent
complete graph
36
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
37
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
38
a walk with no repeated edge.
trail
39
graph with vertex degrees all even.
EVEN GRAPH
40
vertex is odd [even] when its degree is odd?
odd graph/ odd vertex
41
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
42
it has a closed traversable trail. โ€ข Theorem: A graph G is Eulerian if and only if each vertex has an even degree
Eulerian Graph
43
A graph with a closed path that passes through all vertices exactly once.
HAMILTONIAN GRAPH
44
when we do not specify the first vertex but keep the list in cyclic order.
circuit
45
graph is a circuit or trail containing all the edges.
Eulerian circuit or Eulerian trail
46
circuit that uses every edge, but never uses the same edge twice, is called an
euler circuits
47
a path that uses every edge once and only once
euler path
48
This path visits each vertex once and returns to the starting vertex without visiting any vertex twice.
Hamiltonian circuit.
49
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
50
is so called because it has us choose the โ€œcheapestโ€ option at every chance we get
greedy algorithm
51
Use the ____ to find a Hamiltonian circuit
edge-picking algorithm