graphs

graph defintion

pair (v, e) where v is a set of vertices and e is a set of edges

each edge is associated with how many verticies

two which are the endpoints of the edge

weighted graphs provide what

distnace between vertices as well as edges

directed edge

ordered pair of vertices (u, v) where u is origin and v is destination

undirected edge

unordered pair of vertices (u, v)

directed graph

set of vetices v and set of directed edges e

undirected graph

set of not directionally oriented edges (no arrows)

applications of graphs

electronic circuits, transportation networks, computer networks, databases

end vertices or endpoints of an edge

u and v are the endpoints of a

edges incident on a vertex

a, d, and b are incident on v

adjacent vertices

u and v are adjacent

degree of a vertex

x has 5

parallel edges

self-loop

when is a graph connected

if for any two vertices there is a path from one vertex to another

when is a graph disconnected

it its not connected

when does a directed path of length n exist if a directed graph

if and only if there is a sequence of vertices

simple path

all vertices in path are distinct

cycle in directed graph

directed path of the length at least 1 which starts and temrinates at the same vertex

self-lopp has a cycle of length what

1

outdegree

number of vertices adjacent to it or the number of edges leaving the vertex

indegree

number of edges entering the vertex

sink vertex

vertex with outdegree ero

source

vertex with indegree zero

acyclic graph

graph without cycles

strongly connected diagraph

for any two vertices I and J in

the graph there are directed paths from I to J and from J to I.

wealky connedted/semi-connected

or any two

vertices I and J there is a directed path from I to J or from J to I.

simple grpah

no self-lopps and multiple edges

if undirected graph has m edges then the max number of edges is

each edge is counted twize

if undirected graph has n vertices and m edge sthen

m <= n(n-1)/2

if undirected graph with n verticies and m edges is connected then m

m ≥ n − 1

if undirected graph with n verticies and m edges is a tree then m

m = n − 1

if undirected graph with n verticies and m edges is a forest then m

m ≤ n − 1

if directed graph with edges then

each edge contributes once to indegree and once to outdegree of a given vertex

if a directed graph with n vertices and m edges then m

m ≤ n(n − 1). every edge in an undirected graph can be replaced by two edges in a correspoinding directed grpah

depth-first search

all of a vertex descents are processed ebfore moving to an adjacent vertex

breadth first search

all of the adjacent vertices fo a vertex are processed before processing the descendants of the vertex

common representations of a graph

adjacent amtrix and adjacent list

when is a vertex v adjacent to u

if there is and edge from u to v

what does a vertex object contain

element, reference to position in vertex sequence

edge object

element, origin: vertex object, destination: vertex object, reference to position in edge sequence

vertex sequence

sequence of vertex objects

edge sequence

sequence of edge objects

incidence sequence for each vertex

sequence of references to edge objects of incident edges

augmented edge

objects references to associated positions in incidence sequences of end vertices

edge list structure

• augmented vertex objects

• integer key(index) associated with vertex

• 2d array adjacency array

• reference to edge object for adjacent vertices. null for non-adjacent vertices

efficiency of bfs if graph represented using adjacencymatrix

O(|V |^2)

efficiency of bfs if graph represented using adjacency list

o(|V| + |E|)

efficiency of dfs if graph represented using adjacencymatrix

O(|V |^2)

efficiency of dfs if graph represented using adjacency list

o(|V| + |E|)

weighted graph or network

graph whose edges are weighted

meaning of weights depends on the applications

weight of a path of length n from the vertex i to j

the sum of weights of all consecutive weights of edges on this path

minimum spnaning tree

tree that contains all the vertices in the grpah and total weight of edges is the minimum