Graphs

Question 1

What is a graph?

Answer 1

A graph is a set of nodes joined by a set of lines and arrows.

Question 2

Network Theory

Answer 2

Provides a set of techniques for analysing graphs.

Question 3

Complex systems network theory

Answer 3

Techniques for analysing structure in a system of interacting agents, represented as a network.

Question 4

Definition of a Graph

Answer 4

A graph is a set of ordered triples G = (V, E, f) where V is a set of vertices. E is a set, whose elements are edges. f is a function which map each element of E to an unordered pair of vertices in V.

Question 5

Simple Graph

Answer 5

A graph without multiple edges or self-loops.

Question 6

Directed Graph

Answer 6

A graph where edges have directions so an edge is an ordered apir of nodes.

Question 7

Weighted graph

Answer 7

A graph where each edge has an associated weight, usually given by a weight function.

Question 8

Global structural metrics

Answer 8

Refer to a whole graph

Question 9

Local structural metrics

Answer 9

Refer to a single node in a graph

Question 10

Connected graph

Answer 10

Means you can get from any node to any other by following a sequence of edges or any two nodes are connected by a path.

Question 11

Strongly Connected Directed Graph

Answer 11

There is a directed path from any node to any other node.

Question 12

Components

Answer 12

Disconnected graphs can be split into their connected components.

Question 13

Degree

Answer 13

Number of edges incident on a node

Question 14

In-Degree

Answer 14

Number of edges entering

Question 15

Out-degree

Answer 15

Number of edges leaving

Question 16

Degree Properties

Answer 16

If G has m edges then deg(v) = 2m = 2|E|.
If G is a digraph then indeg(v) = outdeg(v)= |E|

Number of odd degree nodes is even

Question 17

Walks

Answer 17

A walk of length k in a graph is a succession of k edges of the form uv, vw, wx, …, yz.

This walk is denoted by uvwx…xz and is referred to as a walk between u and z.

A walk is closed if u=z.

Question 18

Path

Answer 18

A walk in which all the edges and all the nodes are different.

Question 19

Cycle

Answer 19

A closed walk in which all the edges are different.

Question 20

Empty Graph

Answer 20

Has no edges

Question 21

Null graph

Answer 21

No nodes so no edges either.

Question 22

Trees

Answer 22

Connected Acyclic Graphs

Question 23

Regular Graph

Answer 23

Connected graph where all nodes have the same degree.

Question 24

Bipartite Graph

Answer 24

The vertices can be partitioned into 2 sets V1 and V2 such that (u,v) e E implies either u e V1 and v e V2 or v e V1 and u e V2

Question 25

Complete Graph

Answer 25

Every pair of vertices is adjacent.

Question 26

Complete Bipartite Graph

Answer 26

Every node of one set is connected to every node on the other set.

Question 27

Planar Graphs

Answer 27

Can be drawn on a plane such that no two edges intersect

Question 28

Subgraph

Answer 28

Vertex and edge sets are subsets of those of G

Question 29

Supergraph

Answer 29

A graph that contains G as a subgraph.

Question 30

Clique

Answer 30

A maximum complete connected subgraph.

Question 31

Spanning Subgraph

Answer 31

Has the same vertex set as G.

Question 32

Spanning ree

Answer 32

A spanning tree in G is a subgraph of G that includes every node and is also a tree.

Question 33

Isomorphic Graphs

Answer 33

An isomorphism is a bijection or one-to-one mapping. If an isomorphism can be constructed between two graphs then we say those graphs are isomorphic.

Question 34

Adjacency List

Answer 34

An array of V lists, one for each vertex in V. For each U e V, ADJ[u] points to all its adjacent vertices.

Question 35

Topological Distance

Answer 35

The topological distance between nodes p and q is the number of edges in the shortest path connecting them.

Question 36

Random Graph Degree

Answer 36

If a graph has N nodes and a pair of nodes has probabilty p of being connected. The average degree of the graph is therefore k ~= pN.

Question 37

If connections between people can be modelled as random graph then average pathlength between connected nodes is:

Answer 37

lnN/lnk where N is number of people and k is average degree per node i.e. the average number of people you know.