Graphs and graph theory in computer science By Alex Allain What is a graph?
A graph is a way of representing connections between places. Mathematically, a graph is a collection of nodes and edges. Nodes are locations that are connected together by the edges of the graph. For instance, if you had two small towns connected by a two-way road, you could represent this as a graph with two nodes, each node representing a town, and one edge, the road, connecting the two towns together. In addition to the undirected graph, in which the edge is a two-way connection, there are directed graphs, in which edges connect only one way. For instance, you could represent the previous example of two cities connected by a road as a directed graph consisting of two nodes and two edges, each edge connecting one of the nodes to the other. In the city example, it may also be convenient to record the distance between the two cities; this can be expressed by adding a 'weight' to an edge, which is a number that usually corresponds to the distance covered by an edge (the distance between two nodes).
Why are graphs useful?  Computer scientists have developed a great deal of theory about graphs and operations on them. One reason for this is because graphs can be used to represent many problems in computer science that are otherwise abstract. Finding a way to represent the solution to a problem as a graph can present new approaches to solving the problem or even lead directly to a solution derived from graph theory. This sort of technique is often used when discussing algorithmic efficiency and when trying to prove that a certain algorithm is NP-Complete; because many problems involving graphs, such as finding the shortest path to traverse all nodes (the Traveling Salesman Problem), are NP-Complete, if you can find a way to represent a problem as a graph and show that it is analogous to one of the other NP-Complete problems, then you can show the problem you are trying to solve is also NP-Complete, which gives you a hint that the solution will take a great deal of time.
Another reason for using graphs is that many problems computers are used to solve involve representing relationships between objects, places, or concepts. Because graphs can be either directed or undirected, they are a flexible method of showing connections. For instance, you can describe who knows whom in a room as a collection of nodes, each representing a person, and directed edges, each representing that one person knows another. Because graphs are so often used and because they allow the representation of many problems in computer science, such as the Traveling Salesman Problem or something as simple as the relationships between people in a room, they are a convenient means of expressing problems with which many people are comfortable. This familiarity simplifies the process of creating mental models of problems, which ultimately leads to better problem solving. What are some important graph theory terms? Directed Graph: A directed graph is one in which edges connect nodes in only one direction. Undirected Graph: An undirected graph is one in which edges connect nodes bidirectionally (in both directions). Node: A node, usually drawn as a circle, represents an item that can be related to other items or nodes. Nodes are sometimes referred to as vertices. Edge: An edge represents a connection between nodes. Edges can be either directed or undirected, depending on the type of graph. Edges can also have weights, which may correspond to strength of relationship or distance between edges. (For instance, if a graph represents a map, then the weights of each edge will represent the distance between two nodes.) Connected: A graph is connected if from any node you can reach any other node. Disconnected: A graph is disconnected if certain groups of nodes form an island that has no connection to the rest of the graph. Related Articles Dijkstra's Algorithm for Finding Shortest Paths in Non-Negative Weight Graphs |
