Graph Theory - Grafriron

The graphs in graph theory are not those that visually represent the change in quantity, such as bar graphs, line graphs, or quadratic function graphs. For example, imagine the diagrams of railway networks or road networks. In these diagrams, real directions and distances are ignored, and the diagrams are usually drawn with a lot of simplification. Nevertheless, these diagrams are useful because the information needed is what lines connect stations, and at what station you need to transfer. Other examples include company organizational charts, family trees, tournament pairings, and wiring diagrams of electrical circuits. What is important here is only the connection relationships between things represented by points (each department, parent and child, opponent, resistors and semiconductors). Graph theory is a field that expresses and studies such qualitative relationships, and its application area is very wide, not limited to mathematics. Historically, it started with Euler, who will be mentioned later.

A graph is a figure made up of several points and line segments (which can be curved) connecting them. The points are called vertices, and the line segments are called edges. A graph is said to be connected when any two vertices can be connected by a series of edges starting from one vertex and reaching the other. Intuitively, a connected graph forms a single figure. The question is whether there exists a circular path that passes through all the edges of a connected graph once. This is the problem that Euler came up with in the 18th century as the "Königsberg Bridges Problem." In other words, the question is to think of a walking path that goes around all seven bridges that span the Pregel River in Königsberg (now Kaliningrad, Russia) as shown in Figure A , and returns to the original starting point. Euler considered the parts of the town A, B, C, and D as vertices, and the bridges that connect them as edges connecting these points, and came up with a graph as shown in Figure B. Then, the problem of finding a walking path becomes the problem of finding a circular path in this graph. Euler answered this question by proving the theorem that states, "A connected graph has a tour route if the number of edges going out from each vertex is even, or if two vertices have odd edges and the others are even." In fact, in this problem, the number of edges going out from each vertex is odd. Therefore, if there is another bridge between A and B, there is a tour route (although you cannot return to the original location), and if there is yet another bridge between C and D, there is a tour route that returns to the original location. This theorem is also called the "one-stroke theorem" of graphs, and the converse also holds.

If we consider each vertex of a regular dodecahedron like that shown in Figure C as a city in the world, and each edge as a travel route between them, Hamilton's problem is to find a world travel route along this travel route that passes through each city exactly once, and it is also a problem that travel agents regularly face when travel time and travel costs are taken into consideration. The graph created by the vertices of this regular dodecahedron is a planar graph like that shown in Figure D , so we need to consider a path that passes through each vertex of this graph exactly once. In this case, the path we are looking for is shown by the thick line. A similar problem can be considered for any connected graph, but a solution (such as the one-stroke theorem) for the general case has not yet been found.

A graph is called a planar graph if it can be drawn on a plane such that its edges do not cross each other except at the vertices. If the graph in Figure E is drawn on a plane, any two edges will cross at any point other than the vertices, so it is not a planar graph. Regarding this, Kuratowski has a result that states that "for a graph to be planar, it is necessary and sufficient that it does not contain graphs ① or ② in Figure F as parts of it."

The number of edges going out from a vertex of a graph is called the local degree of that vertex. If the local degree of each vertex Ai of a graph with vertices A ₁ , A ₂ , …, An is ρ(Ai) and the number of edges is N, then

From this, we can see that there is always an even number of points whose local degree is odd. A graph like Figure G is a graph with no closed paths (a path that starts from a point, returns to the beginning, and does not meet itself on the way back), and such connected graphs are called ki, which is a translation of the English word tree. If a tree has n vertices, it has n-1 edges. Therefore, if the number of edges in the tree is N and the number of vertices is n, then r = N-n+1 = 0. However, in a general connected graph, this number r = N-n+1 is not 0, and this r is called the circuit rank of the graph ( Figure H ). The circuit rank of a graph increases as the number of circuits it contains increases, and is a number that indicates the complexity of the graph. This is a topological invariant called the one-dimensional Betti number of this shape.

The four coloring problem (which is a problem to prove that when coloring a map by country, with countries that are bordered by lines being colored in different colors, the maximum number of colors needed is four) is also considered to be part of graph theory as a vertex coloring problem, when each country is treated as a vertex and the vertices corresponding to bordering countries are connected with edges.

[Hiroshi Noguchi]

"Graph Theory" by O. Orr, translated by Hiroshi Noguchi (1970, Kawade Shobo Shinsha)

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

グラフ理論というときのグラフは、棒グラフや折れ線グラフ、また二次関数のグラフのように、量の変化を視覚的に表すときのグラフではない。たとえば鉄道網や道路網の図形を思い浮かべてみよう。そこでは現実の方位や距離などは無視され、かなり省略された図が描かれているのが普通である。それにもかかわらずその図が役にたつのは、必要とされる情報が、駅と駅とが何線で結ばれているかとか、乗り換えは何駅で行えばよいか、というようなことだからである。またたとえば会社の組織図や家系図、トーナメントの組合せ、電気回路の配線図なども同様の事情にある。そこで重要なのは、点で表されるもの（各部所、親や子、対戦相手、抵抗や半導体）の結合関係のみである。グラフ理論は、このような質的関係を表現し、研究する分野であり、応用領域は数学のみにとどまらず非常に広い。歴史的には後に述べるオイラーが出発点である。

　いくつかの点とこれらを結ぶ線分（曲線でもよい）からできる図形をグラフという。このとき点は頂点、線分は辺とよばれる。どの二つの頂点も、一方から出発して他方へと達する辺の列で結べるとき、そのグラフは連結であるという。連結なグラフは直観的には、ひとかたまりの図形をなしている。連結グラフのすべての辺を1回通るような周遊道が存在するかどうかという問題がある。これが18世紀に「ケーニヒスベルクの橋の問題」としてオイラーによって考えられた問題である。すなわち図Aのようなケーニヒスベルク（現、ロシア領カリーニングラード）のプレーゲル川に架かっていた七つの橋をすべて1回ずつ回って元の出発点に戻るような散歩道を考えよという問題である。オイラーは、町のA、B、C、Dの部分を頂点で、それらを結ぶ橋をこれらの点を結ぶ辺とみて、図Bのようなグラフを考えた。すると、散歩道をみいだす問題は、このグラフの周遊道をみいだす問題になる。オイラーは、「各頂点から出る辺の数がすべて偶数であるか、二つの頂点では奇数であるが他は偶数であるならば、連結グラフは周遊道をもつ」という定理を証明して、この問題に否と答えたのである。実際、この問題では各頂点から出る辺の数はすべて奇数である。したがってまた、AとBにもう1本の橋が架かっていれば（元の場所へは戻れないが）周遊道があり、さらにCとDにもう1本の橋が架かっていれば元に戻る周遊道が存在する。この定理はグラフの「一筆書きの定理」ともよばれ、逆も成り立つ。

　図Cのような正十二面体の各頂点を世界の都市とみて、各辺をそれらの間を行き来する旅行路としたとき、この旅行路に沿って各都市をちょうど1回通る世界旅行コースをみいだせというのがハミルトンの問題であり、旅行時間や旅費を考慮に入れれば旅行業者がいつも直面する問題でもある。この正十二面体の頂点のつくるグラフは、図Dのような平面上のグラフとなるので、このグラフの各頂点をちょうど1回通る通路を考えればよい。この場合には太線のような道が求める通路になる。同様な問題が任意の連結グラフで考えられるが、この一般の場合の解（一筆書きの定理のような）はまだ得られていない。

　グラフは、それらの辺が頂点以外では互いに交わることのないように平面に描けるとき平面グラフという。図Eのグラフを平面に描くと、かならずどれかの2辺が頂点以外の点で交わってしまうので、これは平面グラフではない。これに関してクラトウスキーによる、「グラフが平面グラフとなるためには、図Fの①または②のグラフが部分として含まれないことが必要十分である」という結果がある。

　グラフの一つの頂点から出る辺の個数をその頂点における局所次数という。頂点がA₁、A₂、…、Anであるグラフの各頂点Aiの局所次数がρ(Ai)であり、辺の数をNとするならば、

となる。このことから、局所次数が奇数であるような点はかならず偶数個あることがわかる。図Gのようなグラフは、閉じた道（ある点から出発して元に戻り、途中では自身と出会うことのない道）のないグラフであり、こうした連結グラフは英語のtreeを訳して木という。木はn個の頂点をもつとn－1個の辺をもつ。よって木の辺の個数をN、頂点の個数をnとすると、r＝N－n＋1＝0となる。しかし一般の連結グラフでは、この数r＝N－n＋1は0ではなく、このrをそのグラフの回路階数という（図H）。グラフの回路階数は、そのグラフに含まれる回路の数が多くなるほど多くなり、そのグラフの複雑さを示す数である。これは、この図形の一次元ベッチ数とよばれる位相不変量である。

　四色問題(よんしょくもんだい)（地図を国で色分けする場合、線で接する国を違う色で塗るとすると、必要な色の最大数は4である、ということの証明問題）も、各国を頂点に境界を接する国に対応する頂点を辺で結ぶと、頂点の彩色問題としてグラフ理論の一部とみられる。

［野口　廣］

『O・オア著、野口廣訳『グラフ理論』（1970・河出書房新社）』

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例