Simple Graph Theory Flashcards

1
Q

a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices.

A

graph

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

A graph is a collection of points called _____________ and line segments or curves called _________that connect the vertices

A

vertices or nodes
edges

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

an edge connecting a vertex to itself.

A

loop

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

a graph that has an edge connecting every pair of vertices.

A

complete graph

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

Two vertices are _______ if there is an edge joining them.

A

adjacent

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

Graphs are considered as _______if they have same vertices connected in the same way.

A

equivalent

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

an alternating sequence of vertices and edges. It can be seen as a trip from one vertex to another using the edges of a graph.

A

path

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

If a path begins and ends with the same vertex, it is a closed path or a _______

A

circuit or cycle.

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

A graph is _________ if for any two vertices, there is at least one path that joins them.

A

connected

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

an edge that when you remove makes the graph disconnected.

A

bridge

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

a vertex is the number of edges attached to it.

A

degree

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

The diagram below appears in a book in psychology. It is used to indicate ”_________ ” which occur in man- woman relationships.

A

transactions

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

One of the subjects studied by mathematicians is _________. The idea is to color the vertices or edges of a graph in such a way that adjacent vertices or concurrent edges are given different colors.

A

graph coloring

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

The smallest number of colors required to color the vertices of a graph

A

chromatic number of the graph.

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

chromatic number of the graph.

A

Colorable Graph Theorem

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

A graph is 2-colorable if and only if it has no circuits that consist of odd number of vertices.

A

Colorable Graph Theorem.

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

The chromatic number of a planar graph is at most 4.

A

Four-Color Theorem

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

A map can be represented by a graph with the different regions as vertices. Two regions are _____ if they share part of their boundaries.

A

Map Coloring
adjacent

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

The graph representing a map is ____. Hence, it needs only 4 colors.

20
Q
  • a path that passes through every edge exactly once only
  • a path that contains all the edges of the graph
  • begin and end with the odd-degree vertices
A

Euler path

21
Q

A graph has an ______ if and only if no more than two of its vertices have odd degree.

A

Euler path

22
Q

a graph is a closed path that contains all the edges of the graph.

A

Euler circuit

23
Q

A graph that has an Euler circuit is called

24
Q

Eulerian if and only if each vertex has even degree.

A

connected graph

25
Q

a graph is a path passing through each vertex of the graph exactly once.

A

Hamiltonian path

26
Q

If the path is closed, it is called

A

Hamiltonian cycle.

27
Q

If a graph has a Hamiltonian cycle, it is called __________

A

Hamiltonian

28
Q

Every ____________- with more than two vertices has a Hamiltonian circuit. Furthermore, the number of Hamiltonian circuits in a complete graph with n vertices is (n-1)!.

A

complete graph

29
Q

the same if they pass through the same vertices in the same order, regardless of the vertex where they begin and end.

A

Two Hamiltonian circuits

30
Q

a graph in which any two vertices are connected by exactly one path.

31
Q

an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees is known as forest. Each component of a forest is tree.

32
Q

a graph is a tree that results from the removal of as many edges as possible from the original graph without making it disconnected.

A

spanning tree

33
Q

A _____________ for a weighted graph is the spanning tree for the graph that has the smallest possible sum of the weights.

A

minimum spanning tree

34
Q

A ____________ must have one fewer edge than the number of vertices.

A

minimum spanning tree

35
Q

a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which

A

Prim’s algorithm

36
Q

A graph is ______ if it can be drawn in such a way that no edges cross. This means that any two edges can meet only at an endpoint.

37
Q

Four-Color Theorem. The chromatic number of a planar graph is __________.

38
Q

used to depict ”what is in conflict with what”, and colors are used to denote the state of a vertex.

A

GRAPH COLORING

39
Q

the theory of ”partitioning the sets having Internal unreconcilable conflicts.

A

coloring theory

40
Q

Vertex Coloring: It is a way of coloring the vertices of a graph such that no two adjacent __________ share the same color.

41
Q

An edge coloring assigns a color to each edge so that no two adjacent edges share the same color.

A

Edge Coloring

42
Q

a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

A

face coloring

43
Q

The chromatic number of a graph is the minimum number of colors in a proper coloring of that graph. If chromatic number is r then the graph is r-chromatic.

A

Chromatic Number

44
Q

A _________ can be represented by a graph with the different regions as vertices. Two regions are adjacent if they share part of their boundaries.

A

map coloring

45
Q

The graph representing a map is planar. Hence, it needs only _______ colors.