Struktur Diskrit : Model Graf, Jenis Graf, dan Implementasinya
Graphs and Graph Models
What is Graph ( Undirected Graph ) ?
A graph G = (V, E) consists of
- V – a nonempty set of vertices (or nodes) ⇛ represented by point
- Infinite vertex set – Infinite graph
- Finite vertex set – Finite graph
- E – a set of Edges ⇛ represented by line segments or curve
- Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoint.
The way we draw a graph is arbitrary as long as the correct connections between vertices are depicted. Avoid crossing edge.
Example of graph
3 vertices ⇛ V = {a, b, c}
3 edges ⇛ E = {e1, e2, e3} = {(a, a), (a, b), (b, c)}
What is Simple Graph ?
A simple graph contains no loop or parallel edges
- No loop ⇛ Each edge connects two different vertices
- No parallel ⇛ No two edges connect the same pair of vertices
Example of simple graph and not a simple graph
Multigraphs & Pseudographs
Multigraphs
Graph that may have multiple edges connecting the same vertices.
Pseudographs
Graph that may include loops, and possibly multiple edge connecting the same vertices.
What is Directed Graph ?
A graph directed (or digraph) (V, E) consists of
- V – a nonempty set of Vertices (or nodes) ⇛ represented by point
- E – a set of directed Edges ⇛ represents by line segments or curve
Each directed edge associated with an ordered pair of vertices (u, v), which said to start at u and end at v.
- Simple directed graph – a directed graph with no loops and no multiple directed edges
- Directed multigraph – a directed graph with multiple directed edge
- Mixed graph – a graph with both directed and undirected edges.
Example of directed graph
Example : Computer Networks
Summary: Types of Graph & its Structure
How to Graph a Model
When we build a graph model, we need to make sure that we have correctly answered three key questions about the structure of a graph as following:
- Are the edges of graph undirected or directed or both ?
- If the graph is undirected, are multiple edges present that connect the same pair of vertices? If the graph is directed, are multiple directed edges presents ?
- Are loops present ?
Implementations of Graph
Social Networks
Model social structures based on different kinds of relationships between people or groups of people. Individuals or organizations are represented by vertices; relationships between individuals or organizations are represented by edges.
Influence Graph
In studies of group behavior it is observed that certain people can influence the thinking of others. A directed graph called an influence graph can be used to model this behavior. Each person of the group is represented by a vertex. There is a directed edge from vertex a to vertex b when the person represented by vertex a can influence the person represented by vertex b. This graph does not contain loops and it does not contain multiple directed edges.
In studies of group behavior it is observed that certain people can influence the thinking of others. A directed graph called an influence graph can be used to model this behavior. Each person of the group is represented by a vertex. There is a directed edge from vertex a to vertex b when the person represented by vertex a can influence the person represented by vertex b. This graph does not contain loops and it does not contain multiple directed edges.
Acquaintanceship and Friendship Graphs
We can use a simple graph to represent whether two people know each other, that is, whether they are acquainted, or whether they are friends (either in the real world in the virtual world via a social networking site such as Facebook). Each person in a particular group of people is represented by a vertex. An undirected edge is used to connect two people when these people know each other, when we are concerned only with acquaintanceship, or whether they are friends. No multiple edges and usually no loops are used.
We can use a simple graph to represent whether two people know each other, that is, whether they are acquainted, or whether they are friends (either in the real world in the virtual world via a social networking site such as Facebook). Each person in a particular group of people is represented by a vertex. An undirected edge is used to connect two people when these people know each other, when we are concerned only with acquaintanceship, or whether they are friends. No multiple edges and usually no loops are used.
Collaboration Graphs
A collaboration graph is used to model social networks where two people are related by working together in a particular way. Collaboration graphs are simple graphs, as edges in these graphs are undirected and there are no multiple edges or loops. Vertices in these graphs represent people; two people are connected by an undirected edge when the people have collaborated. There are no loops nor multiple edges in these graphs.
Examples:
- Hollywood graph
- Academic collaboration graphs
- In sport
Communication Networks
We can model different communications networks using vertices to represent devices and edges to represent the particular type of communications links of interest.
Call Graph
Graphs can be used to model telephone calls made in a network, such as a long distance telephone network. In particular, a directed multigraph can be used to model calls where each telephone number is represented by a vertex and each telephone call is represented by a directed edge.
Graphs can be used to model telephone calls made in a network, such as a long distance telephone network. In particular, a directed multigraph can be used to model calls where each telephone number is represented by a vertex and each telephone call is represented by a directed edge.
Information Networks
Graphs can be used to model various networks that link particular types of information. Here, we will describe how to model the World Wide Web using a graph. We will also describe how to use a graph to model the citations in different types of documents.
The Web Graph
The World Wide Web can be modeled as a directed graph where each Web page is represented by a vertex and where an edge starts at the Web page a and ends at the Web page b if there is a link on a pointing to b. Because new Web pages are created and others removed somewhere on the Web almost every second, the Web graph changes on an almost continual basis.
The World Wide Web can be modeled as a directed graph where each Web page is represented by a vertex and where an edge starts at the Web page a and ends at the Web page b if there is a link on a pointing to b. Because new Web pages are created and others removed somewhere on the Web almost every second, the Web graph changes on an almost continual basis.
Citation Graphs
Graphs can be used to represent citations in different types of documents, including academic papers, patents, and legal opinions. In such graphs, each document is represented by a vertex, and there is an edge from one document to a second document if the first document cites the second in its citation list. A citation graph is a directed graph without loops or multiple edges.
Graphs can be used to represent citations in different types of documents, including academic papers, patents, and legal opinions. In such graphs, each document is represented by a vertex, and there is an edge from one document to a second document if the first document cites the second in its citation list. A citation graph is a directed graph without loops or multiple edges.
Software Design Applications
Graph models are useful tools in the design of software.
Module Dependency
Graphs A module dependency graph provides a useful tool for understanding how different modules of a program interact. In a program dependency graph, each module is represented by a vertex. There is a directed edge from a module to a second module if the second module depends on the first.
Graphs A module dependency graph provides a useful tool for understanding how different modules of a program interact. In a program dependency graph, each module is represented by a vertex. There is a directed edge from a module to a second module if the second module depends on the first.
Precedence Graphs and Concurrent Processing
Computer programs can be executed more rapidly by executing certain statements concurrently. It is important not to execute a statement that requires results of statements not yet executed. The dependence of statements on previous statements can be represented by a directed graph. Each statement is represented by a vertex, and there is an edge from one statement to a second statement if the second statement cannot be executed before the first statement. This resulting graph is called a precedence graph.
Computer programs can be executed more rapidly by executing certain statements concurrently. It is important not to execute a statement that requires results of statements not yet executed. The dependence of statements on previous statements can be represented by a directed graph. Each statement is represented by a vertex, and there is an edge from one statement to a second statement if the second statement cannot be executed before the first statement. This resulting graph is called a precedence graph.
Biological Networks
Many aspects of the biological sciences can be modeled using graphs.
Niche Overlap Graphs in Ecology
Graphs are used in many models involving the interaction of different species of animals. For instance, the competition between species in an ecosystem can be modeled using a niche overlap graph. Each species is represented by a vertex. An undirected edge connects two vertices if the two species represented by these vertices compete (that is, some of the food resources they use are the same). A niche overlap graph is a simple graph because no loops or multiple edges are needed in this model.
Graphs are used in many models involving the interaction of different species of animals. For instance, the competition between species in an ecosystem can be modeled using a niche overlap graph. Each species is represented by a vertex. An undirected edge connects two vertices if the two species represented by these vertices compete (that is, some of the food resources they use are the same). A niche overlap graph is a simple graph because no loops or multiple edges are needed in this model.
Protein Interaction Graphs
A protein interaction in a living cell occurs when two or more proteins in that cell bind to perform a biological function. Because protein interactions are crucial for most biological functions, many scientists work on discovering new proteins and understanding interactions between proteins. Protein interactions within a cell can be modeled using a protein interaction graph (also called a protein–protein interaction network), an undirected graph in which each protein is represented by a vertex, with an edge connecting the vertices representing each pair of proteins that interact.
A protein interaction in a living cell occurs when two or more proteins in that cell bind to perform a biological function. Because protein interactions are crucial for most biological functions, many scientists work on discovering new proteins and understanding interactions between proteins. Protein interactions within a cell can be modeled using a protein interaction graph (also called a protein–protein interaction network), an undirected graph in which each protein is represented by a vertex, with an edge connecting the vertices representing each pair of proteins that interact.
Tournaments
Graphs can also be used to model different kinds of tournaments.
Round-Robin Tournaments
A tournament where each team plays every other team exactly once and no ties are allowed is called a round-robin tournament. Such tournaments can be modeled using directed graphs where each team is represented by a vertex. Note that (a, b) is an edge if team a beats team b. This graph is a simple directed graph, containing no loops or multiple directed edges (because no two teams play each other more than once).
A tournament where each team plays every other team exactly once and no ties are allowed is called a round-robin tournament. Such tournaments can be modeled using directed graphs where each team is represented by a vertex. Note that (a, b) is an edge if team a beats team b. This graph is a simple directed graph, containing no loops or multiple directed edges (because no two teams play each other more than once).
Single-Elimination Tournaments
A tournament where each contestant is eliminated after one loss is called a single-elimination tournament. Single-elimination tournaments are often used in sports, including tennis championships and the yearly NCAA basketball championship. We can model such a tournament using a vertex to represent each game and a directed edge to connect a game to the next game the winner of this game played in.
A tournament where each contestant is eliminated after one loss is called a single-elimination tournament. Single-elimination tournaments are often used in sports, including tennis championships and the yearly NCAA basketball championship. We can model such a tournament using a vertex to represent each game and a directed edge to connect a game to the next game the winner of this game played in.
Posting Komentar