Chapter 28 Flashcards
What is the formula of digraph and undirected graph
G = (V, E)
Where E = Number of edges
What is path in graph
A path in directed graph is a sequence of vertices
What is the length of path
Number of edges
What is cycle in graph
A cycle in a digraph is a path containing at least one edge and for which v0 = v k
What is Hamiltonian cycle in graph
A Hamiltonian cycle is a cycle that visits every vertex in a graph exactly once
What is Eulerian cycle in graph
A Eulerian cycle is a cycle that visits every edge of the graph exactly once
What is acyclic graph
A graph is said to be acyclic if it contains no cycles
What is directed acyclic graph (DAG)
A directed graph that is acyclic is called a directed acyclic graph (DAG).
What are two ways of representing graphs
1- Using an adjacency matrix
2- Using an adjacency list
What is the storage of Adjacency matrix
Q(n2)
What is the storage of adjacency list
Q (n + e)
What is hop in path
Edge
What is degree of vertex
In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.
