コトバンクはYahoo!辞書と技術提携しています。

グラフ理論 ぐらふりろん

7件 の用語解説(グラフ理論の意味・用語解説を検索)

ASCII.jpデジタル用語辞典の解説

グラフ理論

点とそれらを結ぶ線によって表される対象をグラフといい、このグラフの性質を分析するもの。グラフは道路や電気回路などにも見られ、グラフ理論は適用範囲が広い。

出典|ASCII.jpデジタル用語辞典
それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

デジタル大辞泉の解説

グラフ‐りろん【グラフ理論】

いくつかの点(ノード)と、これらを結ぶ線分(エッジ)からなる図形の、位相幾何学的性質を解析する数学理論。歴史的には18世紀、レオンハルト=オイラーの「ケーニヒスベルクの橋」という、七つの橋を1回ずつ渡って出発点に戻る道筋を考える問題に始まる。電気回路・交通問題・パズルなどに応用。

出典|小学館 この辞書の凡例を見る
監修:松村明
編集委員:池上秋彦、金田弘、杉崎一雄、鈴木丹士郎、中嶋尚、林巨樹、飛田良文
編集協力:曽根脩
(C)Shogakukan Inc.
それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

百科事典マイペディアの解説

グラフ理論【グラフりろん】

一筆書きの絵のように,いくつかの点とそれらを結ぶ線からなる図形がグラフである。線は何本あってもよく,グラフを考えるときは,線のつながり方が重要であって形は問題としない。

出典|株式会社日立ソリューションズ・クリエイト
All Rights Reserved. Copyright (C) 2015, Hitachi Solutions Create,Ltd. ご提供する『百科事典マイペディア』は2010年5月に編集・制作したものです

世界大百科事典 第2版の解説

グラフりろん【グラフ理論 theory of graphs】

一筆書きの絵のように,いくつかの点とそれらを結ぶ線からなる図形がグラフである。線は何本あってもよく,曲がっていてもよいし長短もとわないことは電気系統の配線図と同様である。グラフを考えるときは,線のつながり方が重要であって形は問題としないが,線が余分に別な点を通るように変形したり,くぐらせるべきところを交わらせたりすれば別なグラフと考える。このようにグラフに対して許される変形を限定しておいて,それによって不変である性質を研究するのがグラフ理論である。

出典|株式会社日立ソリューションズ・クリエイト
All Rights Reserved. Copyright (C) 2015, Hitachi Solutions Create,Ltd. 収録データは1998年10月に編集製作されたものです。それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。また、本文中の図・表・イラストはご提供しておりません。

大辞林 第三版の解説

グラフりろん【グラフ理論】

有限個の要素からなる集合上の二項関係を研究する数学の一分野。1736年にオイラーによってその端緒が開かれ、計算機科学の発達とともに重要性が認識された。特に、地図色分けに関する定理(四色定理)は、この分野の重要な結果の一つ。

出典|三省堂
(C) Sanseido Co.,Ltd. 編者:松村明 編 発行者:株式会社 三省堂 ※ 書籍版『大辞林第三版』の図表・付録は収録させておりません。 ※ それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

ブリタニカ国際大百科事典 小項目事典の解説

グラフ理論
グラフりろん
graph theory

グラフのもつ位相幾何学的な性質を解析する数学の一分野。ここでのグラフとは,折れ線グラフ棒グラフのように量の変化を図形に表示することをさすのではなく,一筆書きのように,点と線との結合様式によって得られる図形をグラフと定義する。

本文は出典元の記述の一部を掲載しています。

出典|ブリタニカ国際大百科事典 小項目事典
Copyright (c) 2014 Britannica Japan Co., Ltd. All rights reserved.
それぞれの記述は執筆時点でのもので、常に最新の内容であることを保証するものではありません。

日本大百科全書(ニッポニカ)の解説

グラフ理論
ぐらふりろん

グラフ理論というときのグラフは、棒グラフや折れ線グラフ、また二次関数のグラフのように、量の変化を視覚的に表すときのグラフではない。たとえば鉄道網や道路網の図形を思い浮かべてみよう。そこでは現実の方位や距離などは無視され、かなり省略された図が描かれているのが普通である。それにもかかわらずその図が役にたつのは、必要とされる情報が、駅と駅とが何線で結ばれているかとか、乗り換えは何駅で行えばよいか、というようなことだからである。またたとえば会社の組織図や家系図、トーナメント組合せ、電気回路の配線図なども同様の事情にある。そこで重要なのは、点で表されるもの(各部所、親や子、対戦相手、抵抗や半導体)の結合関係のみである。グラフ理論は、このような質的関係を表現し、研究する分野であり、応用領域は数学のみにとどまらず非常に広い。歴史的には後に述べるオイラーが出発点である。
 いくつかの点とこれらを結ぶ線分(曲線でもよい)からできる図形をグラフという。このとき点は頂点、線分は辺とよばれる。どの二つの頂点も、一方から出発して他方へと達する辺の列で結べるとき、そのグラフは連結であるという。連結なグラフは直観的には、ひとかたまりの図形をなしている。連結グラフのすべての辺を1回通るような周遊道が存在するかどうかという問題がある。これが18世紀に「ケーニヒスベルクの橋の問題」としてオイラーによって考えられた問題である。すなわち図Aのようなケーニヒスベルク(現ロシア領カリーニングラード)のプレーゲル川に架かっていた七つの橋をすべて1回ずつ回って元の出発点に戻るような散歩道を考えよという問題である。オイラーは、町のA、B、C、Dの部分を頂点で、それらを結ぶ橋をこれらの点を結ぶ辺とみて、図Bのようなグラフを考えた。すると、散歩道をみいだす問題は、このグラフの周遊道をみいだす問題になる。オイラーは、「各頂点から出る辺の数がすべて偶数であるか、二つの頂点では奇数であるが他は偶数であるならば、連結グラフは周遊道をもつ」という定理を証明して、この問題に否と答えたのである。実際、この問題では各頂点から出る辺の数はすべて奇数である。したがってまた、AとBにもう1本の橋が架かっていれば(元の場所へは戻れないが)周遊道があり、さらにCとDにもう1本の橋が架かっていれば元に戻る周遊道が存在する。この定理はグラフの「一筆書きの定理」ともよばれ、逆も成り立つ。
 図Cのような正十二面体の各頂点を世界の都市とみて、各辺をそれらの間を行き来する旅行路としたとき、この旅行路に沿って各都市をちょうど1回通る世界旅行コースをみいだせというのがハミルトンの問題であり、旅行時間や旅費を考慮に入れれば旅行業者がいつも直面する問題でもある。この正十二面体の頂点のつくるグラフは、図Dのような平面上のグラフとなるので、このグラフの各頂点をちょうど1回通る通路を考えればよい。この場合には太線のような道が求める通路になる。同様な問題が任意の連結グラフで考えられるが、この一般の場合の解(一筆書きの定理のような)はまだ得られていない。
 グラフは、それらの辺が頂点以外では互いに交わることのないように平面に描けるとき平面グラフという。図Eのグラフを平面に描くと、かならずどれかの2辺が頂点以外の点で交わってしまうので、これは平面グラフではない。これに関してクラトウスキーによる、「グラフが平面グラフとなるためには、図Fまたはのグラフが部分として含まれないことが必要十分である」という結果がある。
 グラフの一つの頂点から出る辺の個数をその頂点における局所次数という。頂点がA1、A2、…、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・河出書房新社)』

出典|小学館 日本大百科全書(ニッポニカ) この辞書の凡例を見る
(C)Shogakukan Inc.
それぞれの解説は執筆時点のもので、常に最新の内容であることを保証するものではありません。

グラフ理論の関連キーワード補外法一筆書き一筆絵一筆限り一筆書枝分れケーニヒスベルクの橋影絵のようにフュフナーの式組合せ理論

今日のキーワード

パラチオン、パラチオンメチル

パラチオンは無色で油状の液体、パラチオンメチルはコハク色の液体。ともに毒性が強く、有機リン系殺虫剤として使用された。50年代以降、稲の害虫被害を防ぐことが確認され、広く導入された。しかし、農民の中毒死...

続きを読む

コトバンク for iPhone

グラフ理論の関連情報