1. A graph is a non-linear data structure, which consists of vertices (or nodes) connected by edges (or arcs) where edges may be directed or undirected.
Types of Graphs:
Though there are a lot of different types of graphs in discrete mathematics, there are some that are extremely common. Some of those are as follows:
1. Null graph: Also called an empty graph, a null graph is a graph in which there are no edges between any of its vertices.
2. Connected graph: A graph in which there is a path of edges between every pair of vertices in the graph. Mary's graph is a connected graph, since there is a way to get from every city on the map to every other city.
3.Disconnected graph: A graph in which the path of edges does not always connect every vertex.
4. Bipartite graph: A graph that can be split into two sets of vertices such that edges only go between sets, not within them.
5. Weighted graph: A graph in which weights, or numerical values, are assigned to each of the edges. Mary's graph is a weighted graph, where the distances between the cities are the weights of the edges.
6.Directed graph: A graph in which the edges are directed by arrows, indicating that the relationship, represented by the edge, only applies from one vertex to the other, but not the other way around. In other words, if a directed edge has an arrow from A to B, A is related to B, but B is not related to A.
7.Undirected graph: A graph whose edges are not directed. Mary's graph is an undirected graph, because the routes between cities go both ways.
8. Simple graph: An undirected graph in which there is at most one edge between each pair of vertices, and there are no loops, which is an edge from a vertex to itself.
9. Multi-graph: A graph in which there are multiple edges between any pair of vertices or there are edges from a vertex to itself, also called a loop.
10. Planar graph: A graph that can be drawn so that all of the edges of the graph do not cross each other.
11. Nonplanar graph: A graph that is not a planar graph. In other words, a graph that cannot be drawn without at least one pair of its edges crossing.
2. Application of Graph;
In Computer science graphs are used to represent the flow of computation.
1.Google maps uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices.
2. In Facebook, users are considered to be the vertices and if they are friends then there is an edge running between them. Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of undirected graph.
3. In World Wide Web, web pages are considered to be the vertices. There is an edge from a page u to other page v if there is a link of page v on page u. This is an example of Directed graph. It was the basic idea behind Google Page Ranking Algorithm.
4. In Operating System, we come across the Resource Allocation Graph where each process and
resources are considered to be vertices. Edges are drawn from
resources to the allocated process, or from requesting process to the requested resource. If this leads to any formation of a cycle, then a deadlock will occur.
Picture of 201-15-3293 Abdur Razzak
In reply to Md Assaduzzaman
Re: Answer the question
by 201-15-3293 Abdur Razzak - Thursday, 3 December 2020, 10:59 PM
Picture of DS-(PC-J) Picture of DSLab-(PC-J)
1. Answer:
Graph is a non-linear data structure that is same as the mathematical (discrete mathematics) concept of graphs. It is a collection of nodes (also called as vertices) and edges that connect these vertices. Graphs are used to represent arbitrary relationship among objects. A graph can be directed or undirected.
There are several different types of charts and graphs. The four most common are probably line graphs, bar graphs and histograms, pie charts, and Cartesian graphs.
2. Answer:
The application of graph:
1. In Computer science graphs are used to represent the flow of computation.
2. Google maps uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices.
3. In Facebook, users are considered to be the vertices and if they are friends then there is an edge running between them. Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of undirected graph.
4. In World Wide Web, web pages are considered to be the vertices. There is an edge from a page u to other page v if there is a link of page v on page u. This is an example of Directed graph. It was the basic idea behind Google Page Ranking Algorithm.
5. In Operating System, we come across the Resource Allocation Graph where each process and
resources are considered to be vertices. Edges are drawn from
resources to the allocated process, or from requesting process to the requested resource. If this leads to any formation of a cycle then a deadlock will occur.
Picture of Ordha Nafiz Akbar15-3166
In reply to Md Assaduzzaman
Re: Answer the question
by Ordha Nafiz Akbar15-3166 - Thursday, 3 December 2020, 11:58 PM
Picture of DS-(PC-F)
1. A graph is a non-linear data structure, which consists of vertices (or nodes) connected by edges where edges may be directed or undirected.
Types of Graphs:
Though there are a lot of different types of graphs in discrete mathematics, there are some that are extremely common. Some of those are as follows:
1. Null graph.
2. Connected graph.
3.Disconnected graph.
4. Bipartite graph.
5. Weighted graph.
6.Directed graph.
8. Simple graph.
9. Multi-graph.
2. Application of Graph -
In Computer science graphs are used to represent the flow of computation.
1.Google maps uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices.
2. In Facebook, users are considered to be the vertices and if they are friends then there is an edge running between them. Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of undirected graph.
3. In World Wide Web, web pages are considered to be the vertices. There is an edge from a page u to other page v if there is a link of page v on page u. This is an example of Directed graph. It was the basic idea behind Google Page Ranking Algorithm.
4. In Operating System, we come across the Resource Allocation Graph where each process and
resources are considered to be vertices. Edges are drawn from
resources to the allocated process, or from requesting process to the requested resource. If this leads to any formation of a cycle, then a deadlock will occur.