Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

algorithms > graphs > Flashcards

graphs Flashcards

1
Q

graphs application in general

A

1-0 computer networks
2- electrical circut
3-road maps

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

graphs uses in computer sciences

A

1-Social network (Facebook, LinkedIn)
2-Computer networks
3-Transportation network
4-Wireless sensors

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

Graph Categorization

A

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

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

when do we call a graph multi-graph

A

If the same pair of vertices have more than one edge, that graph is called multi-graph

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

a dircted graph :
(1, 4) = 1→4 where ….. is the tail and …… is the head vertics

A

1 and 4

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

name of edges in dircted and undircted graphs

A

The edges in a digraph are called Arcs or Directed Edges

the edges in undircted graph are called Undirected Edges

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

what is digraph

A

dircted graph

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

graph terminoalgy define all below
1- adjacent vertices
2-incidents
3-loop or(……complete)
4-simple graph

A

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

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

graph terminoalgy(part2) define all below
1-path
2-reachable vertices
3-simple bath

A

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

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

graph terminoalgy part 3
define whats below
1-length
2-circut
3-cycle

A

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.

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

T or F: there can be morew than one path between two vertices

A

T

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

graph terminoalgy part 4
define whats below
1-degree of the vertics
2-in-degree
3-out-degree
4-subgraph
5connected graph

A

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

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

what is the subgraph of this graph

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

graph terminoalgy (Last part)
1- connected graph
2- tree
3-forest

A

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

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

is this a forest or tree and why

A

its forest since tree needs to be connected

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

The Spanning Tree of a Graph G is a …………………

A

subgraph of G that is a tree and contains all the vertices of G.

16
Q

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

A

➢➢ 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

17
Q

➢ Example: Find the adjacency matrices of the following graphs.

A
18
Q

➢➢ |Draw the matrix for this graph

A
19
Q

a graph can be a set of …..

A

trees

19
Q

how to build a tree on the graph

A

Pick a vertex as the root
Choose certain edges to produce a tree
Note: might also build a forest if graph is not connected

19
Q

goal of graph searching is
BFS
DFS

A

methodically explore every vertex and every edge

19
Q

what is ➢ Adjacency List

and what happens to ➢ Adjacency List
in wighted graphs

A

➢➢ 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

20
Q

write pusodocode for BFS

A
20
Q

what kind of queue is implemented in bfs

A

FIFO

21
Q

analysis of BFS

A

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.

22
Q

BFS: Properties

A

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.

23
Q

what type of search :Edges are explored out of the most recently discovered vertex v that still has unexplored edges.

A

DFS

23
Q

which search algo Expand deepest unexpanded node.

A

DFS

24
Q

DFS charsterstics

A

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

25
Q

how is space complextiy in BFS compared to DFS and what is the time complexty in both

A

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

25
Q

BFS and DFS - comparisons

A

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

26
Q

which (search) algorthim can produce minmum spanning tree

A

BFS and DFS both are able to generate MST

27
Q

write psuodocode for DFS algorthim

A
28
Q

what is Strongly Connected Components

A

algorithms (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions