Lesson 2 Flashcards
A _G, consists of two sets V and E.
V is a finite non-empty set of vertices. V(G) = {Vi, Vj…Vn} E is the set of pairs of vertices. E(G) = {(Vi,Vj),(Vk,Vl…)} These pair of vertices are called edges.
Graphs
Kinds of Graphs
Undirected Graph
Directed Graph
The pair of vertices representing any edge in unordered.
Uses a pair of parentheses to denote an edge in an _ graph
(V1, V2) = (V2, V1)
Undirected Graph
The pair of vertices representing any edge is ordered.
Uses angled brackets to denote edges in a _ graph
Also known as digraph
<V1,V2> != <V2, V1>
<V1,V2> where V1 = tail, V2 = head.
Directed Graph
The maximum number of edges in any n vertex is n(n-1)/2
Undirected Graph
The maximum number of edges in any n vertex is n(n-1).
Directed Graph
A “walk” from one vertex to another along directed edges.
Path
A path wherein all vertices except the first and the last are distinct.
Simple Path
A simple path where the first and the last vertices are the same.
Cycle
Degree of a vertex (Directed Graph)
In-degree
Out-degree
The number of edges for which the vertex is the head/2nd component.
In-degree
The number of edges for which the vertex is the tail/1st component.
Out-degree
Number of edges incident to that vertex.
Degree of a vertex (Undirected Graph)
An undirected/directed graph is said to be connected if for every pair of distinct
vertices Vi, Vj in V(G), there is a path from
Vi to Vj.
Connected
A directed graph is said to be strongly connected if for every pair of vertices Vi, Vj in V(G), there is a directed path from Vi to
Vj and from Vj to Vi
Strongly Connected (Directed graph)
an N vertex graph G is a two-dimensional array (NxN), say A, with the property such that A[i,j] = 1 IFF the edge (Vi, Vj) ((<Vi, Vj>) for directed graph) is in E(G). Otherwise, A[i,j]=0
Adjacency Matrix
N rows of the adjacency matrix are
represented as N linked lists. The nodes in each list represented the vertices adjacent from vertex. Each node has at least 2 fields: vertex and link.
Adjacency List
Graph Traversals
DFS (Depth First Search)
BFS (Breadth First Search)
The starting vertex v is visited
An unvisited vertex w adjacent to v is selected and a _from w is initiated
When a vertex u is reached such that all its adjacent vertices have been visited, back up to the last vertex visited which has an unvisited vertex w adjacent to it and initiate _ from w.
The search terminates when no visited vertex can be reached from any of the unvisited ones.
DFS (Depth First Search)
Starting at vertex v and marking it as visited. In _, all unvisited vertices adjacent to v are visited next.
Then, the unvisited adjacent to these vertices are visited and so on.
BFS (Breadth First Search)
A connected non-cyclic graph
A minimal connected subgraph (by minimal, it means one with the fewest number of edges.)
Any tree consisting solely of edges in the graph including all vertices in the graph.
Spanning Trees
Finding a spanning tree with the cost.
The cost of the spanning tree is the sum of all the costs of the edges in that tree
One approach = algorithm
Minimum Cost Spanning Trees
Kruskal’s
The minimum cost spanning tree is built, edge by edge. An edge is included in the tree if it does not form a cycle with edges
already in the tree.
Kruskal’s ALgorithm
