# 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

2
Q

the greatest mathematician
that Switzerland has ever
produced

A

LEONHARD EULER

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

4
Q

: a region

A

A vertex

5
Q

: a path(bridge) between two regions

A

An edge

6
Q

A relation between an edge and a pair of vertices

A

graph

7
Q

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

A

order

8
Q

The number of edges in G, ๐(๐บ)

A

size

9
Q

๐ฝ(๐ฎ )

A

vertex set

10
Q

๐ฌ(๐ฎ )

A

edge set

11
Q

An edge whose endpoints are equal

A

loop

12
Q

Edges have the same pair of endpoints

A

multiple edges

13
Q

A graph has no loops or multiple edges

A

Simple graph

14
Q

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

A

15
Q

a graph whose vertex set and edge set are
finite

A

finite graph

16
Q

the graph whose vertex set and edges are
empty

A

null graph

17
Q

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

A

equivalent graphs

18
Q

A simple graph
โข ๐(๐บโ) = ๐(๐บ)
โข ๐ธ(๐บโ) = { ๐ข๐ฃ | ๐ข๐ฃ ๏๐ธ(๐บ) }

A

complement

19
Q

a set of pairwise adjacent vertices (a
complete subgraph)

A

Clique in a graph

20
Q

a set of pairwise

A

independent set in a graph

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
- X(G) = 3

A

chromatic number

23
Q

a partition of the plane into connected regions

A

map

24
Q

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

A

SCHEDULING AND
GRAPH COLORING

25
Q

a sequence of distinct vertices such that two

A

path

26
Q

a closed Path

A

cycle

27
Q

The assignment of endpoints to edges in H is the
same as in G

A

subgraph

28
Q

There exists at least one path between two
vertices

A

connected

29
Q

there is no path between two vertices

A

disconnected

30
Q

The vertices vj and vk

A

31
Q

The edge ei
is said to be ___upon vj

A

incident

32
Q

vertex vk
is the number of edges incident
upon vk
. It is denoted as d(vk)

A

Degree

33
Q

the n-by-n
matrix in which entry ai,j is the number of edges in G
with endpoints {vi
, vj}

A

34
Q

the n-by-m matrix in which
entry mi,j is 1 if vi
is an endpoint of ei and otherwise is 0

A

incidence matrix

35
Q

a simple graph whose vertices are

A

complete graph

36
Q

is a simple bipartite
graph such that two vertices are adjacent if and only if
they are in different partite sets.

A

biclique or complete bipartite graph

37
Q

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 .

A

walk

38
Q

a walk with no repeated edge.

A

trail

39
Q

graph with vertex degrees all even.

A

EVEN GRAPH

40
Q

vertex is odd [even] when its degree is odd?

A

odd graph/ odd vertex

41
Q

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.

A

TRAVERSABLE GRAPH

42
Q

it has a closed traversable trail.
โข Theorem: A graph G is Eulerian if and only if each vertex
has an even degree

A

Eulerian Graph

43
Q

A graph with a closed path that passes through all
vertices exactly once.

A

HAMILTONIAN GRAPH

44
Q

when we do not specify the
first vertex but keep the list in cyclic order.

A

circuit

45
Q

graph is a circuit
or trail containing all the edges.

A

Eulerian circuit or Eulerian trail

46
Q

circuit that uses every edge, but never uses the same
edge twice, is called an

A

euler circuits

47
Q

a path that uses
every edge once and only once

A

euler path

48
Q

This path visits each vertex once and returns to the
starting vertex without visiting any vertex twice.

A

Hamiltonian circuit.

49
Q

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.

A

diracโs theorem

50
Q

is so called because it
has us choose the โcheapestโ option at every
chance we get

A

greedy algorithm

51
Q

Use the ____ to find a Hamiltonian
circuit

A

edge-picking algorithm