Graph Theory

Question 1

graph

Answer 1

A graph, G=(V,E) is a finite set of vertices V and a finite set of Edges E where each edge (u,v) connects two vertices, u and v.

Question 2

Adjacent

Answer 2

Two vertices, u and v of a graph are adjacent if there exists an edge (u,v).

Question 3

Self loop

Answer 3

A self-loop is an edge (u,u).

Question 4

multi-graph

Answer 4

A multi graph can have multiple edges between the same two vertices and self loops.

Question 5

Incident

Answer 5

If (u,v) is an edge in a graph G, (u,v) is an incident to vertices u and v.

Question 6

Degree

Answer 6

A degree of a vertex is the number of edges incident on it.

Question 7

isolated

Answer 7

A vertex who’s degree is 0 is isolated.

Question 8

Simple path

Answer 8

A path is simple if all vertices in the path are distinct.

Question 9

Subpath

Answer 9

A subpath of a path is a continuous subsequence of its vertices.

Question 10

Path

Answer 10

A path of length k from a vertex u to a vertex u’ is a sequence (v0,v1,v2,…,vk) of vertices such that u=v0, u’=vk and (vi-1,vi) is an edge in E for i=1,2,…,k. The length is the number of edges in the path.

Question 11

Length k

Answer 11

The length is the number of edges in the path.

Question 12

Cycle

Answer 12

A cycle s a path with k>0 where v0=vk, and all the edges are distinct.

Question 13

Simple cycle

Answer 13

A cycle is simple if the vertices are distinct.

Question 14

Acyclic

Answer 14

A graph with no simple cycles is acyclic

Question 15

Connected

Answer 15

A graph is connected if every vertices is reachable from all other vertices

Question 16

Connected components

Answer 16

The connected components are the equivalence classes of vertices under the “is reachable from” relation.

Question 17

Hamiltonian cycle

Answer 17

A Hamiltonian cycle is a simple circuit that traverses all vertices. Named after sir Hamilton 1800s

Question 18

Hamiltonian path

Answer 18

A Hamiltonian path is a simple path that traverses all vertices.

Question 19

Complete graph of n vertices

Answer 19

A complete graph of vertices, Kn in which every pair of vertices is adjacent.

Question 20

Bipartite graph of n vertices

Answer 20

A Bipartite Graph of n vertices is a graph in which the n vertices can be partitioned into two sets V1 and V2 such that for every edge (u, v), u is in one of
the sets and v is in the other. Km,n is the Complete
Bipartite graph where |V1|= m and |V2|= n.

Question 21

Predicate

Answer 21

A predicate is a proposition who’s truth depends on the value of on or more variables of a propositional function. Notation: P(x), Q(x,y), R(a,b,c,d) etc

Question 22

Universe of discourse

Answer 22

The universe of discourse specifies the possible values of the variable(s) in the predicate.

Question 23

Quantifiers

Answer 23

Quantifiers such as E and A are symbols that are used to give more details about the predicate.

Question 24

Universal Quantification

Answer 24

Universal Quantification A of P(x) is the proposition

“P(x) is true for all values of x in some set D”

Question 25

Existential Quantification

Answer 25

Existential Quantification, E of P(x) is the proposition:

“There exists an element in x in some set D such that P(x) is true”