tags : Math, Data Structures, Algorithms, Computation and Computer Theory, Complexity Theory
Intro
 Network that helps define and visualize relationships between various components
 Layout of the graph is not part of the graph. Following two are the same graph
 You can define different networks in the same data. Some networks are more useful than others.
 Possible use
 Can be used in infinite ways. If you can make your data look like a graph, you can reuse a wide variety of graph algorithms.
 Eg. You could represent your game’s economy as a graph, with wheat and bread as nodes and baking as an edge.
 Introduction to Behavior Trees  Game tree  State Game Programming  Polygonal Map Generation
 Graphs and networks  plus.maths.org
Basic terms
 $0(V\*E)$ means that we will check every vertex, and on every vertex we check every edge
 $V$ / Node : Set of vertices
 $E$ / Edge : Set of edges, connection btwn nodes
Path
: Sequence ofvertices
connected byedges
Connectivity
Verted:Connected:
2vertices
areconnected
is there’s apath
connecting themGraph:Connected
: When every node has a path to another nodeConnected Component
Common problems
 Does a path exist
 Is the graph connected
 What’s the shortest path
 Does it contain cycle
 Given a set of k colors, can we assign colors to each vertex so that no two neighbors are assigned the same color? (Sudoku problem)
 Does a path exist that uses every
edge
exactly once?  Does a path exist that uses every
vertex
exactly once? (NP Hard, See Complexity Theory)  Solving the minimum cut problem for undirected graphs  Hacker News
Flavors
 In the diagram, $n(n−1)$, $n(n−1)/2$ is the max number of edges.
Cycle
Cyclic
Path
that starts and ends in the samevertex
. AllCycles
arePath
, but not opposite. A graph can have multiple cycles
 When you start at Node(x), follow the links, and end back at Node(x)
 Needs 3 nodes
 Odd/Even cycles
odd
:odd
no ofvertices
in the cycleeven
:even
no ofvertices
in the cycle
Acyclic
A graph that contains no cycles
DAG
Directed, acyclic graph.
Partite
kpartite
 A graph whose vertices are (or can be) partitioned into k different independent sets.
 Recognition of $k>2$ is NPcomplete
2partite (bipartite)
 aka
2colorable
 If there exists and partition of the vertex set into two
disjointsets
 i.e $V_{1}$ has no adjacent vertices & $V_{2}$ has no adjacent vertices
 If they’re adjacent then one of them is in $V_{1}$ and other one is in $V_{2}$
 Bipartite graphs may be recognized in polynomial time
 Bipartite graphs cannot have any
odd cycles
. i.eodd cycles
not allowed. Eg. triangle has 3
vertices
, and is acycle
. So triangle is not bipartite.
 Eg. triangle has 3
 How to Tell if Graph is Bipartite (by hand)

Types
Complete
: Every vertex in one set is connected to every vertex in the other set.Matching
: Each vertex is connected to at most one other vertex from the opposite set.Planar
: Can be embedded in the plane without any edges crossing.

Links and resources
Others
Regular
: Every vertex has the same degree.Multigraph
: Allows multiple edges between the same pair of vertices. Eg. Being able to swim across a river or take a raft across the same river is an example in games.
Graph representation
Adjacency Matrix
 $G=(V,E)$ with $n$ vertices and $m$ edges
 $M$ is a matrix with $n\texttimesn$
 $M[i,j]=1$ if $(i,j)∈E$
 $M[i,j]=0$ if $(i,j)∈/E$
 Space complexity is $(O(n_{2})$
 Has entry for noedges
 Has double entry for undirected edges
Adjacency List
Nx1
array of pointers Each element(vertex($i$)) points to a linked list of edges incident on vertex $i$
 The direction/order of items in the “edge list” for each “vertex” do not tell anything about if there any network exists between a edge items themselves.
 i.e
A: [B, C]
, this meansA
is connected toB
andC
but tells us nothing about the relation ofB
andC
. This can be confusing becauseB
andC
are next to each other in a link list. In other words, link list is just the implementation and not the logical view.
 i.e
 List contains list of “what am i adjacent to”
 Each vertex (
N
) has set of edges (M
). No of edges per vertex is called thedegree
 So, in a way no. of
neighbors
of somevertex
is thedegree
 So, in a way no. of
 Space complexity
 Sparse
 Space Complexity
 $θ(N+2M)=θ(n)$ (undirected) or $θ(N+M)=θ(n)$ (directed)
 total
N
vertices (items in array)  total
M
edges  In undirected, each connected
N
has the edge mentioned both ways. So2M
 Space Complexity
 Dense
 Space Complexity: $θ(N\*N)=θ(n_{2})$
 Sparse
Graph Nodes
 Graph Nodes etc. like we do with linked list
 But we don’t do it this way in practice generally