1. Different kinds of graphs

Different kinds of graphs

Graph

Graphs are drawings with dots and (not necessarily straight) lines and arrows.

graph A {
	label="multigraph"
	w
	x--y
	x--x,z
	z--x
}
 
graph B {
	label="simple graph"
	a,b--c
	b--d
	a--b
}
 
digraph C {
	label="directed graph"
	1->1,2,3,4
	2->1,2,4
	3->3
}

graph A {
	graph[nodesep="0.5"]
	node[shape=point]
	w[xlabel="w"]
	x[xlabel="x"]
	y[xlabel="y"]
	x[xlabel="x"]
	label="multigraph"
	w
	x--y
	x--x,z
	z--x
}
 
graph B {
	graph[nodesep="0.5"]
	node[shape=point]
	a[xlabel="a"]
	b[xlabel="b"]
	c[xlabel="c"]
	label="simple graph"
	a,b--c
	b--d
	a--b
}
 
digraph C {
	graph[nodesep="0.5"]
	node[shape=point]
	1[xlabel="1"]
	2[xlabel="2"]
	3[xlabel="3"]
	4[xlabel="4"]
	label="directed graph"
	1->1,2,3,4
	2->1,2,4
	3->3
}

Link to original

Vertices

The dots in a graph are called vertices (or nodes).

Link to original

Edges

The lines or arrows in a graph are called edges.

Link to original

graph {
	node [label="node"]
	A--B [label="  edge"]
}

Type	Edges	Multiple edges	Loop edges
(simple) graph	undirected	no	no
multigraph	undirected	yes	yes
directed graph	directed	no	yes

title: Example 1: Niche overlap graphs in ecology
Competitions between species in an ecosystem can be modelled using a **niche overlap graph**.
 
```graphviz
graph N {
	layout=neato
	splines=true
	
	node [shape=point]
	1 [pos="0,0!" xlabel=Racoon]
	2 [pos="1,0!" xlabel=Hawk]
	3 [pos="2,0!" xlabel=Owl]
	4 [pos="0,-1!" xlabel=Opossum]
	5 [pos="1,-1!" xlabel=Squirrel]
	6 [pos="2,-1!" xlabel=Crow]
	7 [pos="0,-2!" xlabel=Shrew]
	8 [pos="1,-2!" xlabel=Mouse]
	9 [pos="2.4,-2!" xlabel=Woodpecker]
 
	1--2,3,5
	2--3,6
	3--6
	4--5,7,9
	5--6,9
	7--8,9
}

title: Example 2: Road networks
 
```graphviz
graph {
	layout=neato
 
	node[shape=point]
	O[xlabel=Oxford, pos="0,0!"]
	L[xlabel=London, pos="3,0!"]
	C[xlabel=Cambridge, pos="0,-3!"]
	B[xlabel=Brighton, pos="3,-3!"]
	
	O--O,L,L,L,C,C
	L--L,B,B
	C--L,L,B
}

title: Example 3: Representing binary relations
$$
	R = \{ (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,4), (3,3) \}
$$
 
```graphviz
digraph A {
	1->1,2,3,4
	2->1,2,4
	3->3
}