graphs Flashcards
graphs application in general
1-0 computer networks
2- electrical circut
3-road maps
graphs uses in computer sciences
1-Social network (Facebook, LinkedIn)
2-Computer networks
3-Transportation network
4-Wireless sensors
Graph Categorization
1-➢ A Directed Graph or Digraph is a graph where each edge has a direction
The edges in a digraph are called Arcs or Directed Edges
.
2-➢ An Undirected Graph is a graph where the edges have no directions
The edges in an undirected graph are called Undirected Edges
3-A Weighted Graph is a graph where all the edges are assigned weights.
4-multi graph If the same pair of vertices have more than one edge, that graph is called
when do we call a graph multi-graph
If the same pair of vertices have more than one edge, that graph is called multi-graph
a dircted graph :
(1, 4) = 1→4 where ….. is the tail and …… is the head vertics
1 and 4
name of edges in dircted and undircted graphs
The edges in a digraph are called Arcs or Directed Edges
the edges in undircted graph are called Undirected Edges
what is digraph
dircted graph
graph terminoalgy define all below
1- adjacent vertices
2-incidents
3-loop or(……complete)
4-simple graph
1- they are called adjecnt when theere is edge that connects thm like (1,4)
2-where there is edge like (1,4)its called an incident
3-loop or self edge when there is an edge thats connected to itself like (4,4) in the last graph
4- A graph that is undirected and does not have any loops or multiple edges
graph terminoalgy(part2) define all below
1-path
2-reachable vertices
3-simple bath
1-path : sequnce of edges in the graph
2-its reachable if there was a path between the two vertices
3-simple path is path where each node is visted once
graph terminoalgy part 3
define whats below
1-length
2-circut
3-cycle
length : sum of the lengtrh of the edges on the path
Circuit: A path whose first and last vertices are the same.
➢➢ The path 3,2,1,4,5,3 is a circuit
➢ Cycle: A circuit where all the vertices are distinct except for the first (and the last) vertex.
➢➢ 1,4,5,3,1 is a cycle, but 1,4,5,4,1 is not a cycle.
➢ Hamiltonian Cycle: A Cycle that contains all the vertices of the graph.
➢➢ 1,4,5,3,2,1 is a Hamiltonian Cycle.
T or F: there can be morew than one path between two vertices
T
graph terminoalgy part 4
define whats below
1-degree of the vertics
2-in-degree
3-out-degree
4-subgraph
5connected graph
1- degree in undircted graph is the number of edges or incicdents
2-in-degree in DIgraph the number of edges entering the vertex
3-out degree the number of edges leaving the vertex
4-sub graph ➢ A Subgraph of graph G=(V,E) is a graph H=(U,F) such that U Є V and F Є E
5-A graph is said to be Connected if there is at least one path from every vertex to every other vertex in the graph
what is the subgraph of this graph
graph terminoalgy (Last part)
1- connected graph
2- tree
3-forest
1-connected graph : if there was at least one path between every vertex in the graph
2-tree :Connected Undircted graph that contains no cycle
3-forest: graph that dose not contain a cycle
is this a forest or tree and why
its forest since tree needs to be connected
The Spanning Tree of a Graph G is a …………………
subgraph of G that is a tree and contains all the vertices of G.
The Adjacency Matrix A=(ai,j) of a graph G=(V,E) with n nodes is an ……. matrix
Each element of A is either ……, depending on the adjacency of the nodes
➢➢ The Adjacency Matrix A=(ai,j) of a graph G=(V,E) with n nodes is an nXn matrix
➢➢ Each element of A is either 0 or 1, depending on the adjacency of the nodes
➢ Example: Find the adjacency matrices of the following graphs.
➢➢ |Draw the matrix for this graph
a graph can be a set of …..
trees
how to build a tree on the graph
Pick a vertex as the root
Choose certain edges to produce a tree
Note: might also build a forest if graph is not connected
goal of graph searching is
BFS
DFS
methodically explore every vertex and every edge
what is ➢ Adjacency List
and what happens to ➢ Adjacency List
in wighted graphs
➢➢ An Adjacency list is an array of lists, each list showing the vertices a given vertex is adjacent to.
in weighted graph its included in the list
write pusodocode for BFS
what kind of queue is implemented in bfs
FIFO
analysis of BFS
The operations of enqueuing and dequeuing take O(1) time. So the total time devoted to queue operations is O(V).
Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once.
Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E).
The overhead for initialization is O(V), and thus the total
running time of BFS is O(V + E).
Thus breadth-first search runs in time linear in the size of the adjacency-list representation of G.
BFS: Properties
BFS calculates the shortest-path distance to the source node
Shortest-path distance δ(s,v) = minimum number of edges from s to v, or ∞ if v not reachable from s.
.
BFS builds breadth-first tree, in which paths to root represent shortest paths in G.
Thus can use BFS to calculate shortest path from one vertex to another in O(V+E) time.
what type of search :Edges are explored out of the most recently discovered vertex v that still has unexplored edges.
DFS
which search algo Expand deepest unexpanded node.
DFS
DFS charsterstics
1-It searches deeper the graph when possible
2-Edges are explored out of the most recently discovered vertex v.
3-When all of vʼs edges have been explored, backtrack to the vertex from which v was discovered.
4- records timestamps for each vertex
d[v] discovered
f[v] when the vertex is finished
how is space complextiy in BFS compared to DFS and what is the time complexty in both
Space complexity of DFS is lower than that of BFS.
Time complexity of both is same – O(|V|+|E|).
.
Diffrent space complexity same time complexity
BFS and DFS - comparisons
BFS produces a single tree that includes all vertices reachable from s.
DFS may produce multiple trees, forming a forest.
.
This is because DFS explores as far as possible along a branch before backtracking, and disconnected components are treated as separate trees.
both can generate MST
which (search) algorthim can produce minmum spanning tree
BFS and DFS both are able to generate MST
write psuodocode for DFS algorthim
what is Strongly Connected Components
