Graphs: Terminology and Definitions Flashcards

1
Q

What is graph?

A

A graph is a mathematical structure consisting of two types of elements

• G = (V,E) where
– V is a set of nodes called vertices
——>The order of a graph is the number of its vertices, i.e. |V|
– E is a collection of edges that connect pairs of vertices
——-> The size of a graph is the number of its edges, i.e. |E|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Edge Types

A
Directed Edge:
– Ordered pair of vertices (u,v)
– First vertex u is the origin
– Second vertex v is the destination
EX: u -------> v

Undirected Edge:
– Unordered pair of vertices (u,v)
EX: u ——– v

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

A graph may be:

A

– Undirected, i.e. there is no distinction between two vertices associated with each edge
EX: edge (3,2) is the same as edge (2,3)

()Directed, i.e. the edges are directed from one vertex to the other
EX: edge (1,2) goes from node 1 to node 2,
1 –> 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Edge components (information)

A
  • Edges may be labeled

- They may have weights, costs, color associated with it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Weighted Undirected graph

A

EX: a network of airports

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Weighted graph

A

It has weights associated with the edges. Numerical weights are sometimes referred to as cost

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Why and when to use graphs over trees?

A
  • Tree can be considered a limited type of graph
  • Trees are useful for describing hierarchical information, but they can only describe information where the parent/child relationship is upheld
  • To describe information that doesn’t meet this criteria we use graphs
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Endpoints (or end vertices) of an edge

A

Two or more edges having a vertex v as at least one of their endpoints are called edges incident to v
EX: (6, 10), (4,10)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Adjacent vertices

A

Two vertices connected by an edge are adjacent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Degree of a vertex

A

It is the number of edges starting or ending at that vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Degree in directed graphs

A

Out-degree: number of edges starting at that vertex

In-degree: number of edges ending at that vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A path

A

A sequence of edges (or of adjacent vertices)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

The length of a path

A

The number of edges on that path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

A simple path

A

A path where all its vertices and edges are distinct

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

A cycle

A

A path beginning and ending at the same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

A simple cycle

A

A cycle which does not pass through any vertex more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

A loop

A

An edge whose endpoints are the same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Labeled graph

A
  • Labels are associated with each edge or each vertex (numbers)
  • Weighted: weights are associated with edges
19
Q

Directed/Undirected graph

A

-All edges are directed/undirected

20
Q

Regular graph

A

All vertices have the same degree

21
Q

Data Structures for vertices

A

– Hash table (generally preferred)
– Array
– List
– Binary search tree

22
Q

Data Structures for edges

A

– Adjacency list

– Adjacency Matrix

23
Q

Adjacency list

A
  • It consists of an array A of |V| lists, one for each vertex in V
  • The vertices in each adjacency list are typically stored in arbitrary order
24
Q

Adjacency Matrix

A

It is a two dimensional array A of dimensions n×n (n is
the number of vertices in G) , where:

–If the graph is directed, then the element a(i,j) is 1 if and only if there is a directed edge from vertex i to vertex j.

– If the graph is undirected, then the element a(i, j) and a(j, i) are 1 if and only if there is an edge from vertex i to vertex j

a(i, j) = 1 if (i, j)∈E 0 if (i, j)∉E

25
Adjacency List vs. Adjacency matrix
• Given graph G=(V,E), the running time of an algorithm it’s often expressed in terms of: – |V| and |E|
26
Adjacency List vs. Adjacency matrix Storage and length
Storagerequired: – Adjacency list ---->If G is a directed graph, the sum of the lengths of all adjacency lists is |E| ----> If G is an undirected graph, the sum of the lengths of all adjacency lists is 2|E| ---->In both cases the memory required is O(V + E) – Adjacency matrix ----->O(V^2)
27
Adjacency List vs. Adjacency matrix running time
* Running time for operations such as inserting an edge, determining if an edge exists, and deleting an edge * Adjacency list all take potentially O(V) * Adjacency matrix all take O(1) •If time is of the essence and these operations predominate, then a matrix may be the best choice
28
Traversing Algorithms
traverse means to visit the vertices in some systematic order ü Preorder - visit each node before its children ü Postorder - visit each node after its children ü Indorder - BST only, visit left subtree, node, right subtree
29
Graph Traversal Algorithms
Breadth-first search (BFS) | Depth-first search (DFS)
30
Breadth-first search (BFS)
General technique for traversing a graph • Archetype for many graph algorithms: – Dijkstra’s shortest path algorithm – Prim’s minimum spanning tree algorithm Idea: Given a graph G and a source vertex s, BFS systematically explores the edges of G to “discover” every vertex that is reachable from s
31
Breadth-first search (BFS) running time
• Time=O(V+E) – O(V) because every vertex dequeued at most once – O(E) because for every vertex dequeued we examine (u, v) • directed graph every edge examined at most once • undirected graph every edge examined at most twice
32
BFS Algorithm | Time=O(V+E)
``` BFS(G, s) for each u ∈ V - {s} do u.dist ← ∞ s.dist ← 0 Initialize empty queue Q ENQUEUE (Q, s) while Q is not empty do u ← DEQUEUE(Q) for each v ∈ Adj[u] do if v.dist = ∞ then v.dist ← u.dist + 1 ENQUEUE (Q, v) ```
33
Depth-first search (DFS)
It is a strategy for exploring a graph Useful for the following problems: ....Testing whether a graph is connected ...Computing a path between two vertices or equivalently reporting that no such path exists .....Computing a cycle or equivalently reporting that no such cycle exists ....Uses a backtracking technique (try each possibility until one is found)
34
DFS vs. BFS
DFS uses a strategy that searches “deeper” in the graph whenever possible, unlike BFS which discovers all vertices at distance k from the source before discovering any vertices at distance k+1
35
DFS Technique
• Depth-first search is like exploring a maze – Follow path until you get stuck ....Backtrack until you reach an unexplored neighbor – Recursively explore – Careful not to repeat a vertex
36
DFS Algorithm Pseudocode O(V+E)
``` DFS(V, E) for each u ∈ V do u.color ← WHITE time ← 0 for each u ∈ V do if u.color = WHITE then DFS-VISIT(u) ``` ``` DFS-VISIT(u) u.color ← GRAY time ← time + 1 u.i ← time for each v ∈ Adj[u] do if v.color = WHITE then DFS-VIST(v) u.color ← BLACK time ← time + 1 u.f ← time ```
37
Edge Classification
* The edge we traverse as we execute DFS can be classified into four types: tree, back, forward, and cross edges * The classification of edge(u,v) depends on whether we have visited v before in the DFS and if so, the relationship between u and v
38
Tree Edge
As we traverse the edge(u, v) if v is visited for the first time, then the edge is a tree edge (u,v) is a tree edge if v was first discovered by exploring edge (u,v). A tree edge always describes a relation between a node and one of its direct descendants. This indicates that u.i < v.i, (u’s discovery time is less than v’s discovery time), so a tree edge points from a “low” to a “high” node.
39
Back Edge
As we traverse the edge(u, v) if v has already been visited: If v is an ancestor of u, then(u, v) is a back edge Back edges are those edges (u,v) connecting a vertex v to an ancestor u. Self-loops are considered to be back edges. Back edges describe descendant-to-ancestor relations, as they lead from “high” to “low” nodes.
40
Forward Edge
As we traverse the edge(u, v) if v has already been visited: If v is an descendant of u, then(u, v) is a forward edge Forward edges are those edges (u,v) connecting a vertex u to a descendant v in a depth-first tree. Forward edges describe ancestor-to-descendant relations, as they lead from “low” to “high” nodes.
41
Cross Edge
As we traverse the edge(u, v) if v has already been visited: If v is neither an ancestor or descendant of u, then(u, v) is a cross edge Cross edges link nodes with no ancestor-descendant relation and point from “high” to “low” nodes.
42
Edge classification facts
• If G is undirected, DFS produces only tree and back edges • G is a directed acyclic graph if and only if DFS yields no back edges --Directed acyclic graph (DAG) is a directed graph with no cycles
43
Cycle detection
A directed graph G contains a cycle if and only if a DFS of G yields a back edge
44
Applications of DFS
* Topological sort * DFS can be used to perform a topological sort of a directed acyclic graph * A topological sort of a DAG is a linear ordering of all its vertices such that if DAG contains an edge (u, v), then u appears before v in ordering