Graph Theory

Question 1

Graph

Answer 1

An ordered pair (V, E) of a set of nodes (vertices) and a set of unordered pairs of nodes (edges)

Question 2

Order of a graph

Answer 2

The number of nodes

Question 3

Degree of a node

Answer 3

The number of edges connected to the node

Question 4

Size of a graph

Answer 4

The number of edges

Question 5

Loop

Answer 5

An edge whose pair of nodes are the same

Question 6

Link or side

Answer 6

An edge whose pair of nodes is different

Question 7

Simple graph

Answer 7

A graph without loops and the same 2 nodes can not be connected by multiple edges

Question 8

Multigraph

Answer 8

A graph where the set of edges is a multiset, meaning the same nodes can be connected multiple times

Question 9

Adjacency Matrix

Answer 9

A way of encoded a simple graph where 1 represents an edge and 0 represents no edge. Row represents the start of the edge and the column represents the end.

Question 10

Chain

Answer 10

The succession of a sequence of alternating nodes and edges, starting and finishing on nodes.

Question 11

The length of a chain

Answer 11

The number of edges it contains

Question 12

The distance between 2 nodes in a graph

Answer 12

The length of the shortest chain between 2 nodes

Question 13

The diameter of a graph

Answer 13

The longest distance between any 2 nodes

Question 14

When is a chain said to be closed?

Answer 14

When the start vertex and the end vertex are the same vertex.

Question 15

What is a connected component of an undirected graph?

Answer 15

A subgraph in which any 2 nodes are connected to each other by a path

Question 16

When is a graph said to be connected?

Answer 16

If it only has 1 connected component

Question 17

When is a graph said to be free?

Answer 17

If it has no edges

Question 18

When is a graph said to be complete?

Answer 18

If every pair of different nodes are connected

Question 19

What is weak connectivity in a directed graph?

Answer 19

If 2 nodes are connected, ignoring the direction of edges

Question 20

What is strong connectivity in a directed graph?

Answer 20

When 2 nodes are connected following edge direction

Question 21

Bridge/Cut-edge

Answer 21

An edge in a graph that if removed increases the number of connected components

Question 22

Cut-vertex/Articulation point

Answer 22

A node in a graph that if removed increases the number of connected components

Question 23

When is a graph said to be regular of degree?

Answer 23

When all of its nodes have the same degree

Question 24

Tree

Answer 24

A graph in which every pair of nodes is joined by a single chain

Question 25

Degree Centrality

Answer 25

The degree of a node is the number of edges it is connected to

Question 26

Betweenness Centrality

Answer 26

The degree of a node is the number of shortest paths between every node in the graph that cross that node

Question 27

Closeness Centrality

Answer 27

The degree of a node is 1 over the average distance to every other node in the graph