Table of Contents
hide
Introduction
- A graph data structure is a mathematical structure but is also used in Computer Science, Physics and Chemistry, Linguistics, Biology, etc.
Definition of Graph
- A graph is a common, complex, non-linear, cyclic, scattered, or non-contiguous, data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them.
- Mathematically, a graph(G) is a pair of sets (V, E). V is a set of arbitrary objects that we call vertices or nodes. E is a set of vertex pairs, which we call edges or occasionally arcs.
- Graphs are mathematical and data structures used in computer science, mathematics, and various other fields to model and represent relationships between objects.
Characteristics of Graph
- The graph data structure comprises more than one vertice (node) connected and communicated by the edges (arcs or lines or links). Nodes are the fundamental building blocks of a graph. Each node represents an object or entity in the graph. Nodes can have labels or values associated with them. Nodes can store data or attributes associated with the represented entities.
- Edges are the connections between nodes in a graph. They represent relationships or associations between the objects defined by the nodes. Edges can be directed or undirected, depending on whether they have a specific direction or not.
Terminology
- Graph Theory :
- The study of graphs is called graph theory.
- Null graph :
- A graph that does not have edges.
- Embedding :
- An embedding of a graph maps each vertex to a point in the plane and each edge to a curve or straight line segment between the two vertices.
- We usually visualize graphs by looking at an embedding.
- Planner graph:
- A graph is said to be planar if it has an embedding where no two edges cross. The same graph can have many different embeddings, so it is important not to confuse a particular embedding with the graph itself.
- When no two edges of a graph intersect and all the vertices and edges are drawn in a single plane, then such a graph is called a planar graph.
- Intersection graph :
- The intersection graph is a collection of objects that has a node for every object and an edge for every intersecting pair.
- Complete graph :
- When each pair of vertices are connected by an edge then such a graph is called a complete graph.
- Finite graph :
- A graph that has a finite number of vertices and edges is called a finite graph.
- Dense graph :
A dense graph is a graph in which the number of edges is close to the maximal number of edges.
- Sparse graph :
- A graph with only a few edges is called a sparse graph.
- Cycle :
- A cycle is a path that starts and ends at the same vertex and has at least one edge.
- A cycle is a path that starts and ends at the same node, forming a closed loop within the graph.
- A cycle is a closed path in a graph that forms a loop.
- When the starting and ending point is the same in a graph that contains a set of vertices, then the cycle of the graph is formed.
- When there is no repetition of the vertex in a closed circuit, then the cycle is formed.
- A cycle that has an even number of edges or vertices is called an Even Cycle.
- A cycle that has an odd number of edges or vertices is called an Odd Cycle.
- Path :
- A path is a sequence of edges, where each successive pair of edges shares a vertex, and all other edges are disjoint.
- A path in a graph is a sequence of nodes where each consecutive pair of nodes is connected by an edge.
- A path in an undirected graph is a sequence of vertices.
- The length of a path is the number of edges it contains.
- Adjacent Vertices:
- Two vertices are said to be adjacent when both are incident to a common edge.
- Adjacent Edges :
If two edges of a graph are connected by a single vertex, they are called adjacent edges.
- Forests :
- Acyclic graphs are also called forests.
- Degree of Node :
- The degree of a node is the number of neighbors.
- The degree of a node is the number of edges incident to it. In directed graphs, nodes can have an in-degree (number of incoming edges) and an out-degree (number of outgoing edges).
- Indegree of a node:
- The in-degree of a node is the number of predecessors, which is the same as the number of edges going into the node.
- Outdegree of a node :
- The out-degree is the number of successors, or the number of edges going out of the node.
- Density of a Graph/Graph Density:
- Graph density is a measure of how many edges are present compared to the maximum possible edges in a graph.
- A dense graph has a high edge-to-node ratio, while a sparse graph has a low edge-to-node ratio.
Type of Graph Data Structure
There are several types of graphs used in daily to daily life works. These are categorized into different groups, depending on several factors. These are –
(A) On the basis of the direction of edge/communication towards the vertex, graphs are of the following types –
(a.) Undirected Graph :
- The edge of this graph has no clear-cut direction i.e. nodes are connected by edges without an arrow symbol rather only with line symbols that are all bidirectional.
- For example – if an edge connects node x and y, we can traverse from node x to node y, and from node y to x.
(b.) Directed Graph(Digraphs) :
- A graph in which nodes are connected by directed edges.
- These directed edges only go in one direction.
- For example, if an edge connects node x and y, but the arrowhead points towards y, we can only traverse from node x to node y and not in the opposite direction.
- Strongly Connected: In a directed graph, every pair of nodes has a directed path between them.
- Weakly Connected: In a directed graph, after ignoring edge directions between every pair of nodes, it becomes only connected.
(B) On the basis of, graphs are of the following types –
(a.) Cyclic Graph :
- A normal graph that contains at least one cycle in its structure.
(b.) Acyclic Graph :
- A graph that does not contain any cycles is called an acyclic graph.
- A special case of an acyclic graph is a tree, which is a connected acyclic graph.
- A graph is acyclic if no subgraph is a cycle.
- Acyclic graphs are also called forests.
(C) On the basis of, graphs are of the following types –
(a.) Connected Graph :
- A graph is considered connected if there is a path between every pair of nodes.
- A graph is called connected if there is a path from any vertex to any other vertex.
- A graph where any two vertices are connected by a path.
(b.) Non-connected Graph :
- A disconnected graph consists of multiple disconnected components, with no path between nodes in different components.
- A graph where any two vertices or nodes are disconnected by a path.
(D) On the basis of, graphs are of the following types –
(a.) Simple Graph :
- A simple graph is a typical graph that is undirected and does not have any loops(there is no edge from a vertex to itself) or multiple edges (there is at most one edge from any vertex to any other).
(b.) Multigraph Graph :
- A graph with multiple edges between the same set of vertices.
- It has a looped graph.
(E) On the basis of, the number of edges relative to the number of nodes Graphs are of the following types –
(a.) Dense Graph :
- Dense graphs have many edges.
(b.) Sparse Graph :
- Sparse graphs have relatively few edges.
Use/Application of Graph
- Graphs are used to solve real-life problems that involve representation of the problem space as a network.
- Graphs have powerful abstractions capability, hence graphs play very important role in modeling data.
- Some of the important applications of graphs are –
- Graphs in Social network :
- The concept of Graph is used in making several social network applications. Here, graphs represent who knows whom, who communicates with whom, who influences whom or other relationships in social structures.
- These can be used to determine how information flows, how topics become hot, how communities develop, or even who might be a good match for who, or is that whom.
- Graphs in Transportation networks :
- The concept of graph is used in making road networks where vertices are intersections and edges are the road segments between them, and for public transportation networks vertices are stops and edges are the links between them. Such networks are used by many map programs such as Google maps, Bing maps and now Apple IOS 6 maps.
- They are also used for studying traffic patterns, traffic light timings, and many aspects of transportation.
- Graphs in Utility :
- The power grid, the Internet, and the water network are all examples of graphs where vertices represent connection points, and edges the wires or pipes between them.
- Analyzing properties of graphs are very important in understanding and finding the reliability of such utilities under failure or attack, or in minimizing the costs to build infrastructure that matches required demands.
- Graphs in Document link graphs :
- The concept of graph is used to represent the technology of hyperlink. The best known example is the link graph of the web, where each web page is a vertex, and each hyperlink a directed edge. Thus, link graphs are used, to analyze relevance of web pages and good link sites.
- Graphs in Protein-Protein interactions graphs :
- Here, the concept of graph’s vertices represent proteins and edges represent interactions between them that carry out some biological function in the cell.
- The graphs can be used, to study molecular pathways—chains of molecular interactions in a cellular process. As we know that humans have over 120K proteins with millions of interactions among them.
- Graphs in Network Packet Traffic graphs :
- Vertices of graph represents IP (Internet protocol) addresses and edges are the packets that flow between them in a network traffic structure.
- The graphs are also used for analyzing network security, studying the spread of worms, and tracking criminal or non-criminal activity.
- Graphs in Scene graphs :
- In graphics and computer games scene graphs represent the logical or spacial relationships between objects in a scene. Thus, graphs are very important in the computer games industry.
- Graphs in Finite element meshes :
- The elements along with the connections between adjacent elements forms a graph that is called a finite element mesh.
- In engineering applications, many simulations of physical systems, such as the flow of air over a car or airplane wing, the spread of earthquakes through the ground, or the structural vibrations of a building, involve partitioning space into discrete elements.
- Graphs in Robot planning :
- In Robot planning, the vertices of graph represent states the robot can be in and the edges the possible transitions between the states. This requires approximating continuous motion as a sequence of discrete steps. Such graph plans are used in planning paths for autonomous vehicles.
- Graphs in Neural networks :
- Neural networks are used to understand how our brain works and how connections change when we learn. The human brain has about 1011 neurons and close to 1015 synapses.
- Here, the concept of vertices represent neurons and edges the synapses between them.
- Graphs in quantum field theory :
- Here, vertices of graph represent states of a quantum system and the edges the transitions between them.
- The graphs can be used to analyze path integrals and summing these up generates a quantum amplitude.
- Graphs in Semantic networks :
- Here, vertices of graph represent words or concepts and edges represent the relationships among the words or concepts. These have been used in various models of how humans organize their knowledge, and how machines might simulate such an organization.
- Graphs in epidemiology :
- Here, vertices of graph represent individuals/patients and directed edges the transfer of an infectious disease from one individual to another. Using the properties of graphs, by analyzing such graphs has become an important component in understanding and controlling the spread of diseases.
- Graphs in compilers :
- Graphs are used extensively in compilers designing. They can be used for type inference, for so called data flow analysis, register allocation and many other purposes.
- They are also used in specialized compilers, such as query optimization in database languages.
- Graphs in Constraint :
- Graphs are often used to represent constraints among items. For
example, the GSM network for cell phones consists of a collection of overlapping cells. Any pair of cells that overlap must operate at different frequencies. These constraints can be modeled as a graph where the cells are vertices and edges are placed between cells that overlap.
- Graphs are often used to represent constraints among items. For
- Graphs in Dependence :
- Graphs can be used to represent dependences or precedences among items. Such graphs are often used in large projects in laying out what components rely on other components and used to minimize the total time or cost to completion while abiding by the dependences.
0 Comments