Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs - Coggle Diagram
Graphs
Informally, a graph is a collection of points in the plane called “vertices” or “nodes,” some of them
connected by line segments called “edges” or “arcs”
Formally, a graph G = [V, E] is defined by a pair of two sets: a finite nonempty set V of items called vertices
and a set E of pairs of these items called edges
If these pairs of vertices are
unordered, i.e., a pair of vertices (u, v) is the same as the pair (v, u), we say that the vertices u and v are adjacent to each other and that they are connected by the
undirected edge (u, v)
We call the vertices u and v endpoints of the edge (u, v)
and say that u and v are incident to this edge; we also say that the edge (u, v) is incident to its endpoints u and v
A graph G is called
undirected
if every edge in
it is undirected
Since our definition disallows multiple edges between the same vertices of
an undirected graph, we have the following inequality for the number of edges |E| possible in an undirected graph with |V| vertices and no loops:
0 ≤ |E| ≤ |V| * (|V| − 1)/2
A graph with every pair of its vertices connected by an edge is called
complete
.
A standard notation for the complete graph with |V| vertices is K|v|
A graph with relatively few possible edges missing is called
dense
; a graph with few edges relative to the number of its vertices is called
sparse
. Whether we are dealing with a dense or sparse graph may influence how we choose to represent the graph and, consequently, the running time of an algorithm being designed or used
If a pair of vertices (u, v) is not the same as the pair (v, u), we say that the
edge (u, v) is directed from the vertex u, called the edge’s tail, to the vertex v called the edge’s head. We also say that the edge (u, v) leaves u and enters v
A graph whose every edge is directed is called directed. Directed graphs are also
called digraphs
In a direct graph, direct paths are usually more important. A directed path is a sequence of vertices in which every consecutive pair of the
vertices is connected by an edge directed from the vertex listed first to the vertex listed next
Graph representations
adjacency lists
adjacency matriz
Weighted graphs
It is a graph with numbers assigned to its edges. These numbers are called weights or costs
A graph is said to be connected if for every pair of its vertices u and v there
is a path from u to v.
If a graph is not connected, such a model will consist
of several connected pieces that are called connected components of the graph
Formally, a connected component is a maximal (not expandable by including another vertex and an edge) connected subgraph of a given graph
A cycle is a path of a positive length that starts and ends at
the same vertex and does not traverse the same edge more than once
Depth-First Search(DFS)
&
Breadth-First Search(BFS)
The term “exhaustive search” can also be applied to two very important algorithms
that systematically process all vertices and edges of a graph
DFS and BFS have proved to be very useful for many applications involving graphs in
artificial intelligence and operations research. In addition, they are very important to investigate properties of graphs, such as, connectivity and cycle presence
DFS starts a graph’s traversal at an arbitrary vertex by marking it
as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in(arbitrary)
As a practical matter, which of the adjacent unvisited
candidates is chosen is dictated by the data structure representing the graph
This process continues until a dead end
(a vertex with no adjacent unvisited vertices)
is encountered
At a dead end, the algorithm backs up one edge to the vertex
it came from and tries to continue visiting unvisited vertices from there
The algorithm eventually halts after backing up to the starting vertex, with the latter
being a dead end
It is convenient to use a stack to trace the operation of depth-first search. We
push a vertex onto the stack when the vertex is reached for the first time and we pop a vertex off the stack when it becomes a dead end
1 more item...
It proceeds in
a concentric manner by visiting first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on, until all
the vertices in the same connected component as the starting vertex are visited
If there still remain unvisited vertices, the algorithm has to be restarted at an
arbitrary vertex of another connected component of the graph
It is convenient to use a queue
to trace the operation of breadth-first search. The queue is initialized with the
traversal’s starting vertex, which is marked as visited
On each iteration, the
algorithm identifies all unvisited vertices that are adjacent to the front vertex, marks them as visited, and adds them to the queue; after that, the front vertex is
removed from the queue
ALGORITHM BFS(G)
//Implements a breadth-first search traversal of a given graph
//Input: Graph G = V,E
//Output: Graph G with its vertices marked with consecutive integers
// in the order they are visited by the BFS traversal
mark each vertex in V with 0 as a mark of being “unvisited”
count ← 0
for each vertex v in V do
if v is marked with 0
bfs(v)
bfs(v)
//visits all the unvisited vertices connected to vertex v
//by a path and numbers them in the order they are visited
//via global variable count
count ← count + 1; mark v with count and initialize a queue with v
while the queue is not empty do
for each vertex w in V adjacent to the front vertex do
if w is marked with 0
count ← count + 1; mark w with count
add w to the queue
remove the front vertex from the queue
Breadth-first search has the same efficiency as depth-first search
1 more item...
Topological Sorting
We will be using directed graphs(or digraphs)
Four types of edges
back edges
from vertices to their ancestors
forward edges
from vertices to their descendants in the tree other than their children
cross edges
Edgdes that don´t fit the other three
Tree edges
"Normal"
A directed cycle in a digraph is a sequence
of three or more of its vertices that starts and ends with the same vertex and in which every vertex is connected to its immediate predecessor by an edge directed from the predecessor to the successor
A topological sorting problem can be modeled by a digraph in which vertices represent courses
and directed edges indicate prerequisite requirements
The problem won´t have a solution if a digraph has a directed cycle
Reversing the order of a DST yields a solution to the topological
sorting problem
The first thing to do in solving a topological sorting problem is to make sure
that the set of given prerequisites is not contradictory