Please enable JavaScript.
Coggle requires JavaScript to display documents.
M10 - Coggle Diagram
M10
Graphs
Collection of vertices/nodes, and pairs of these nodes are called edges
If a pair of vertices (v,u) is not the same as the pair (u,v), the edge connecting the pair is called directed. If every edge in a graph is directed, the graph is called directed. A directed graph may also be called digraph.
If a pair of vertices (v,u) is the same as the pair (u,v), the edge connecting the pair is called undirected. If every edge in a graph is undirected, the graph is called undirected.
-
Graph Representations
Adjacency Matrix
The adjacency matrix of a graph with n vertices is a n x n boolean matrix with one row and one column for each of the graph's vertices, in which the element in the ith row and the jth column is equal to 1 if there is an edge from the ith vertex to the jth vertex, and equal to 0 if there is no such edge.
Adjacency List
The adjacency lists of a graph or digraph is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list's vertex(all the vertices connected to it by an edge). In other words, adjacency lists indicate columns of the adjacency matrix that, for a given vertex, contain 1's.
Weighted Graph
A weighted graph is a graph with numbers assigned to its edges. These numbers are called weights or costs.
If a weighted graph is represented by its adjacency matrix, then its element A[i, j] will simply contain the weight of the edge from the ith to the jth vertex, and a special symbol if there is no such edge. Such a matrix is called weight matrix or cost matrix.
Adjacency lists for a weighted graph have to include in their nodes not only the name of an adjacent vertex but also the weight of the corresponding edge.
Paths and Cycles
There are two important properties of graphs: Connectivity and Acyclicity. Both are based on the notion of a Path. A path from a vertex u to vertex v of a graph G can be defined as the sequence of adjacent vertices that starts with u and ends with v. If all vertices of a path are distinct, the path is said to be simple. The length of a path is the total number of vertices in the vertex sequence defining the path minus 1, which is the same as the number of vertices in the vertex sequence defining the path minus 1, which is the same as the number of edges in the path.
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.
-
Exhaustive Search
Depth-First Search
Depth-first search 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. 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. By then, all the vertices in the same connected component as the starting vertex have been visited. If unvisited vertices still remain, the depth-first search must be restarted at any one of them.
Breadth-First Search
Breadth-first search 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.