グラフ‐りろん【グラフ理論】
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/04 07:43 UTC 版)
グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。
- ^ 概念
- ^ ハイパーリンク
- ^ (ラテン語) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128–140. Konigsberg Bridge problemを参照。
- ^ Diestel, p. 20
- ^ グラフ理論の歴史を扱っているBiggs et al. (1998)にオイラーの論文の英訳を含む節がある。
- ^ 詳しくは、一筆書きの項を参照。
- ^ 無向グラフと有向グラフ
- ^ a b c d ディーステル 2000, 1.1 グラフ
- ^ Bondy & Murty 2008, p. 50.
- ^ ディーステル 2000, p. 10.
- ^ 多重グラフ
- ^ ベルジュ「グラフの理論I」p.8.
- ^ ディーステル, 2000
- ^ 茨木「アルゴリズムとデータ構造」
- ^ ディーステル 2000, p. 6.
- ^ Bondy & Murty 2008, p. 80.
- ^ 閉路
- ^ Diestel, p. 115
- ^ Hale, Scott A. (2013). “Multilinguals and Wikipedia Editing”. Proceedings of the 2014 ACM Conference on Web Science - WebSci '14: 99–108. arXiv:1312.0976. doi:10.1145/2615569.2615684. ISBN 9781450326223.
- ^ Mashaghi, A. (2004). “Investigation of a protein complex network”. European Physical Journal B 41 (1): 113–121. arXiv:cond-mat/0304207. Bibcode: 2004EPJB...41..113M. doi:10.1140/epjb/e2004-00301-0.
- ^ a b Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M et al. (2019-07-01). “Characterizing the role of the structural connectome in seizure dynamics” (英語). Brain 142 (7): 1955–1972. doi:10.1093/brain/awz125. ISSN 0006-8950.
- ^ Grandjean, Martin (2016). “A social network analysis of Twitter: Mapping the digital humanities community”. Cogent Arts & Humanities 3 (1): 1171458. doi:10.1080/23311983.2016.1171458.
- ^ Vecchio, F (2017). “"Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data”. Brain Imaging and Behavior 11 (2): 473–485. doi:10.1007/s11682-016-9528-3. PMID 26960946.
- ^ Vecchio, F (2013). “Brain network connectivity assessed using graph theory in frontotemporal dementia”. Neurology 81 (2): 134–143. doi:10.1212/WNL.0b013e31829a33f8.
- ^ “TextGraphs: Graph-based Algorithms for Natural Language Processing”. 2019年7月26日閲覧。
- ^ Bjorken, J. D.; Drell, S. D. (1965). Relativistic Quantum Fields. New York: McGraw-Hill. p. viii
- ^ Kumar, Ankush; Kulkarni, G. U. (2016-01-04). “Evaluating conducting network based transparent electrodes from geometrical considerations”. Journal of Applied Physics 119 (1): 015102. Bibcode: 2016JAP...119a5102K. doi:10.1063/1.4939280. ISSN 0021-8979.
- ^ Grandjean, Martin (2015). "Social network analysis and visualization: Moreno’s Sociograms revisited". Redesigned network strictly based on Moreno (1934), Who Shall Survive.
- ^ Rosen, Kenneth H. (2011-06-14). Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill. ISBN 978-0-07-338309-5
- ^ Fritsch (2012), p. 99
- ^ “高校「新学習指導要領」は教え方改革 - 旺文社 教育情報センター”. eic.obunsha.co.jp. 2019年2月1日閲覧。
- ^ “国公立大学 2025年度 2次試験・個別学力検査 入試科目”. www.keinet.ne.jp. 河合塾. 2023年6月21日閲覧。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/02/11 06:13 UTC 版)
位相的グラフ理論（英語版）では、頂点 n 個、m 本の辺、k 個の連結成分をもったグラフ G の 1次ベッチ数は、m − n + k に等しい。 このことは、辺の数についての数学的帰納法により直接証明ができる。つまり、新しい辺 1-サイクル分の数を増やすが、もしくは辺の連結成分の数を一つ減らすかのどちらかである。 第一ベッチ数は、グスタフ・キルヒホフ(Gustav Kirchhoff)がベッチ(Betti)の論文以前に導入した用語であるサイクロマチック数（英語版）(cyclomatic number)とも呼ばれる。第一ベッチ数のソフトウェア工学への応用は、循環的複雑度を参照のこと。 グラフの第 0 番めのベッチ数は、連結成分の数 k を単純に意味している。
※この「グラフ理論」の解説は、「ベッチ数」の解説の一部です。
「グラフ理論」を含む「ベッチ数」の記事については、「ベッチ数」の概要を参照ください。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/17 06:09 UTC 版)
グラフを n 個のハンドルのついた球面（種数 n の向き付け可能閉曲面）上で辺同士が交差することなく描けるとき、最小の n をグラフの種数と呼ぶ。したがって、平面グラフは単純な球面上に交差することなく描けるので、種数は0である。 グラフを n 個のクロスキャップのついた球面（種数 n の向き付け不可能閉曲面）上で辺同士が交差することなく描けるとき、最小のnをグラフの向き付け不可能種数と呼ぶ。 位相幾何学的グラフ理論においては、群の種数のいくつかの定義がある。Arthur T. White は次のような概念を提唱した。すなわち群の種数 G {\displaystyle G} は、 G {\displaystyle G} の任意の（連結かつ無向の）ケイリーグラフの種数のうち最小のものである。 グラフの種数を求める問題はNP完全問題である (Thomassen 1989)。
※この「グラフ理論」の解説は、「種数」の解説の一部です。
「グラフ理論」を含む「種数」の記事については、「種数」の概要を参照ください。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/01 07:43 UTC 版)
図のような無向グラフの隣接行列は [ 1 1 0 1 0 1 0 1 0 ] {\displaystyle {\begin{bmatrix}1&1&0\\1&0&1\\0&1&0\end{bmatrix}}} である。 有限グラフの隣接行列はグラフ理論における基本的な概念である。これは枝によって繋がれたグラフの頂点を表す。また、距離行列は頂点間の距離に関する情報を含む。このような概念はハイパーリンクによって繋がれたウェブサイトや道路で繋がれた都市といった場面で応用することができる。このようなことからネットワーク理論においても行列は用いられることとなる。
※この「グラフ理論」の解説は、「行列」の解説の一部です。
「グラフ理論」を含む「行列」の記事については、「行列」の概要を参照ください。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/13 01:37 UTC 版)
グラフ理論の言葉を使うなら、次のようなことである。 WWW上の各ページをノードと見なし、リンクをエッジと見なした有向グラフを考える。 この有向グラフの隣接行列を転置したものを A =(aij) とし、行列 B = (bij) を b i j = a i j / ∑ k a k j {\displaystyle b_{ij}=a_{ij}{\bigg /}\textstyle \sum _{k}a_{kj}} で定義する。 B の最大固有値に属する固有ベクトルを求める。固有ベクトルの各要素の値が、求めるべき各ページの得点である。 補足すると、上の定義において、B は A の各要素をその列の非零要素の数で割ったものである。 従って、B の各列の和は 1 になっている。 B は推移確率行列と呼ばれ、あるページからあるページへリンクによってジャンプする確率を表しているものと考えられる。
※この「グラフ理論」の解説は、「ページランク」の解説の一部です。
「グラフ理論」を含む「ページランク」の記事については、「ページランク」の概要を参照ください。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 00:56 UTC 版)
グラフ理論ではY-Δ変換は、グラフ中のYのサブグラフを同等のΔのサブグラフに置き換えることである。この変換はグラフのエッジの数を増加させることは無いが、グラフのノードの数を増加させる。2つのグラフは、Y-Δ変換と逆変換を行い、もとに戻るのであるなら、Y-Δ等価であるという。例えば、ピーターセングラフはY-Δ等価なクラスである。 この項目は、電子工学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（Portal:エレクトロニクス）。
※この「グラフ理論」の解説は、「Y-Δ変換」の解説の一部です。
「グラフ理論」を含む「Y-Δ変換」の記事については、「Y-Δ変換」の概要を参照ください。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/05 03:40 UTC 版)
※この「グラフ理論」の解説は、「接続行列」の解説の一部です。
「グラフ理論」を含む「接続行列」の記事については、「接続行列」の概要を参照ください。
グラフ理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/14 20:57 UTC 版)
結婚定理はグラフ理論にも応用される。グラフ理論の用語で問題を表すと次のようになる。 有限な2部グラフ G:= (X + Y, E) で X と Y が同じ大きさとしたとき、マッチングは存在するか? すなわち、G の各頂点が必ず1つの辺と接合するような辺の集合は存在するか? 結婚定理がこの問題の答えを与える。 G の頂点の集合 W について、G における W の近傍を N G ( W ) {\displaystyle N_{G}(W)} で表す。近傍とは、W の何らかの元に隣接する全頂点の集合である。グラフ理論における結婚定理（ホールの定理）によれば、完全マッチングが存在することと X のあらゆる部分集合 W について次が成り立つことは同値である。 | W | ≤ | N G ( W ) | {\displaystyle |W|\leq |N_{G}(W)|} 言い換えれば、X のあらゆる部分集合 W は Y に属する頂点と十分に隣接している。 任意のグラフに一般化したものがタットの定理である。
※この「グラフ理論」の解説は、「ホールの定理」の解説の一部です。
「グラフ理論」を含む「ホールの定理」の記事については、「ホールの定理」の概要を参照ください。
グラフ理論と同じ種類の言葉
固有名詞の分類
- グラフ理論のページへのリンク
