In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graphs that are commonly considered. The graphs studied in graph theory should not be confused with graphs of functions or other kinds of graphs.
Graphs are one of the prime objects of study in Discrete Mathematics.
Applications of Graphs
Graph Theory is one of the branch of Discrete Mathematics. This subject nor- mally studies some discrete phenomenons. The phenomenon is said to be discrete when it only deals with some discontinued ¯nite elements. The integer set is usually considered to be a discrete object. Discrete Mathematics Model grows intensively in all aspect of modern society. One of the factors is due to the ad- vance of information and communication technology. The data storage system in computer is manipulated in discrete format. Some examples fragmently categorized as Discrete Mathematics Model are Com-putation Models, Algorithm Complexity, Graph Representation, and many oth- ers. In this book, we focus on the study of graph modeling. The use of graph in many ¯eld is to model a real phenomenon, for examples chemical compound representation, computer database, programming debugging, KÄonigsberg bridge problem, and utilities problem.
1. Chemical Compound
A chemical compound is a pure chemical substance consisting of two or more different chemical elements that can be separated into simpler substances by chemical reactions. Chemical compounds have a unique and defined chemical structure; they consist of a fixed ratio of atoms that are held together in a defined spatial arrangement by chemical bonds. Chemical compounds can be molecular compounds held together by covalent bonds, salts held together by ionic bonds, intermetallic compounds held together by metallic bonds, or complexes held together by coordinate covalent bonds. Pure chemical elements are not considered chemical compounds, even if they consist of molecules which contain only multiple atoms of a single element (such as H2, S8, etc.), which are called diatomic molecules or polyatomic molecules.
2. KÄonigsberg Bridge Problem
The Seven Bridges of Königsberg is a notable historical problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology.
The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.
The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side). Euler proved that the problem has no solution.
3. utilities problem
The phrase "water, gas, and electricity" may refer in general to a public utility. Sewer, Gas, & Electric is also the title of a science fiction novel by Matt Ruff.
The classical mathematical puzzle known as water, gas, and electricity, the (three) utilities problem, or sometimes the three cottage problem, can be stated as follows:
Suppose there are three cottages on a plane (or sphere) and each needs to be connected to the gas, water, and electric companies. Using a third dimension or sending any of the connections through another company or cottage are disallowed. Is there a way to make all nine connections without any of the lines crossing each other?.
0 komentar:
Posting Komentar