Chapter 6 - Mathematics of Graphs

Question 1

The greatest mathematician that Switzerland has ever produced.

Answer 1

LEONHARD EULER

Question 2

A branch of mathematics concerning with network of points connected by lines

Answer 2

MATHEMATICS OF GRAPH

Question 3

It is ultimately the study of relationships

Answer 3

MATHEMATICS OF GRAPH

Question 4

an object

Answer 4

Vertex

Question 5

a relation between two objects

Answer 5

Edge

Question 6

vertex set

Answer 6

V(G)

Question 7

edge set

Answer 7

E(G)

Question 8

The number of vertices in G is called?

Answer 8

Order

Question 9

The number of edges in G is called?

Answer 9

Size

Question 10

An edge whose endpoints are equal

Answer 10

Loop

Question 11

Edges have the same pair of endpoints

Answer 11

Multiple edges

Question 12

A graph has no loops or multiple edges

Answer 12

Simple graph

Question 13

A graph whose vertex set and edge set are finite

Answer 13

Finite graph

Question 14

The graph whose vertex set and edges are empty

Answer 14

Null graph

Question 15

a set of pairwise adjacent vertices (a complete subgraph)

Answer 15

Clique

Question 16

a set of pairwise nonadjacent vertices

Answer 16

Independent set

Question 17

A graph G is “ “ if V(G) is the union of two disjoint independent sets called partite sets of G

Answer 17

bipartite

Question 18

The chromatic number of a graph G, written as?

Answer 18

x(G)

Question 19

the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors

Answer 19

Chromatic number

Question 20

is a partition of the plane into connected regions

Answer 20

map

Question 21

a sequence of distinct vertices such that two consecutive vertices are adjacent

Answer 21

Path

Question 22

a closed Path

Answer 22

Cycle

Question 23

A subgraph of a graph G is a?

Answer 23

graph H

Question 24

There exists at least one path between two vertices

Answer 24

Connected

Question 25

There exists are no path between two vertices

Answer 25

Disconnected

Question 26

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

Answer 26

adjacency matrix

Question 27

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

Answer 27

incidence matrix

Question 28

adjacency matrix of G is written as?

Answer 28

A(G)

Question 29

incidence matrix is written as?

Answer 29

M(G)

Question 30

a simple graph whose vertices are pairwise adjacent

Answer 30

Complete Graph

Question 31

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

Answer 31

Complete bipartite graph (biclique)

Question 32

a walk with no repeated edge.

Answer 32

trail

Question 33

is a graph with vertex degrees all even.

Answer 33

even graph

Question 34

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

Answer 34

odd

Question 35

A graph that can be drawn without any breaks in the curve without repeating any edge.

Answer 35

TRAVERSABLE GRAPH

Question 36

The graph is “ “ if it has a closed traversable trail.

Answer 36

Eulerian graph

Question 37

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

Answer 37

HAMILTONIAN GRAPH

Question 38

a closed trail containing all edges.

Answer 38

Eulerian

Question 39

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

Answer 39

Circuit

Question 40

a graph is a circuit or trail containing all the edges.

Answer 40

Eulerian curcuit

Question 41

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

Answer 41

Euler Circuit

Question 42

This path visits each vertex once and returns to the starting vertex without visiting any vertex twice. We call such a path a?

Answer 42

Hamiltonian circuit

Question 43

A graph that contains a Hamiltonian circuit is called?

Answer 43

Hamiltonian

Question 44

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

Answer 44

equivalent graphs

Question 45

A graph G is bipartite if V(G) is the union of two disjoint independent sets called

Answer 45

partite sets of G

Question 46

choose the cheapest option at every chance we get.

Answer 46

The greedy algorithm

Question 47

Mark the edge of smallest weight in the graph.

Answer 47

THE EDGE-PICKING ALGORITHM