Graphs Flashcards
What is a graph?
A graph is a set of nodes joined by a set of lines and arrows.
Network Theory
Provides a set of techniques for analysing graphs.
Complex systems network theory
Techniques for analysing structure in a system of interacting agents, represented as a network.
Definition of a Graph
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.
Simple Graph
A graph without multiple edges or self-loops.
Directed Graph
A graph where edges have directions so an edge is an ordered apir of nodes.
Weighted graph
A graph where each edge has an associated weight, usually given by a weight function.
Global structural metrics
Refer to a whole graph
Local structural metrics
Refer to a single node in a graph
Connected graph
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.
Strongly Connected Directed Graph
There is a directed path from any node to any other node.
Components
Disconnected graphs can be split into their connected components.
Degree
Number of edges incident on a node
In-Degree
Number of edges entering
Out-degree
Number of edges leaving
Degree Properties
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
Walks
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.
Path
A walk in which all the edges and all the nodes are different.
Cycle
A closed walk in which all the edges are different.
Empty Graph
Has no edges
Null graph
No nodes so no edges either.
Trees
Connected Acyclic Graphs
Regular Graph
Connected graph where all nodes have the same degree.
Bipartite Graph
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
Complete Graph
Every pair of vertices is adjacent.
Complete Bipartite Graph
Every node of one set is connected to every node on the other set.
Planar Graphs
Can be drawn on a plane such that no two edges intersect
Subgraph
Vertex and edge sets are subsets of those of G
Supergraph
A graph that contains G as a subgraph.
Clique
A maximum complete connected subgraph.
Spanning Subgraph
Has the same vertex set as G.
Spanning ree
A spanning tree in G is a subgraph of G that includes every node and is also a tree.
Isomorphic Graphs
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.
Adjacency List
An array of V lists, one for each vertex in V. For each U e V, ADJ[u] points to all its adjacent vertices.
Topological Distance
The topological distance between nodes p and q is the number of edges in the shortest path connecting them.
Random Graph Degree
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.
If connections between people can be modelled as random graph then average pathlength between connected nodes is:
lnN/lnk where N is number of people and k is average degree per node i.e. the average number of people you know.
