Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CMMW > Chapter 6 - Mathematics of Graphs > Flashcards

Chapter 6 - Mathematics of Graphs Flashcards

1
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
2
Q

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

A

MATHEMATICS OF GRAPH

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

It is ultimately the study of relationships

A

MATHEMATICS OF GRAPH

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

an object

A

Vertex

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

a relation between two objects

A

Edge

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

vertex set

A

V(G)

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

edge set

A

E(G)

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

The number of vertices in G is called?

A

Order

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

The number of edges in G is called?

A

Size

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

An edge whose endpoints are equal

A

Loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
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
12
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
13
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
14
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
15
Q

a set of pairwise adjacent vertices (a complete subgraph)

A

Clique

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

a set of pairwise nonadjacent vertices

A

Independent set

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

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

A

bipartite

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

The chromatic number of a graph G, written as?

A

x(G)

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

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

A

Chromatic number

20
Q

is a partition of the plane into connected regions

A

map

21
Q

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

A

Path

22
Q

a closed Path

A

Cycle

23
Q

A subgraph of a graph G is a?

A

graph H

24
Q

There exists at least one path between two vertices

A

Connected

25
Q

There exists are no path between two vertices

A

Disconnected

26
Q

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

A

adjacency matrix

27
Q

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

28
Q

adjacency matrix of G is written as?

A

A(G)

29
Q

incidence matrix is written as?

A

M(G)

30
Q

a simple graph whose vertices are pairwise adjacent

A

Complete Graph

31
Q

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

A

Complete bipartite graph (biclique)

32
Q

a walk with no repeated edge.

A

trail

33
Q

is a graph with vertex degrees all even.

A

even graph

34
Q

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

A

odd

35
Q

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

A

TRAVERSABLE GRAPH

36
Q

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

A

Eulerian graph

37
Q

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

A

HAMILTONIAN GRAPH

38
Q

a closed trail containing all edges.

A

Eulerian

39
Q

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

A

Circuit

40
Q

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

A

Eulerian curcuit

41
Q

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

A

Euler Circuit

42
Q

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

A

Hamiltonian circuit

43
Q

A graph that contains a Hamiltonian circuit is called?

A

Hamiltonian

44
Q

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

A

equivalent graphs

45
Q

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

A

partite sets of G

46
Q

choose the cheapest option at every chance we get.

A

The greedy algorithm

47
Q

Mark the edge of smallest weight in the graph.

A

THE EDGE-PICKING ALGORITHM

CMMW (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions