ブラウザよりも高速アクセス！
89 関係: 名称のあるグラフのギャラリー、存在グラフ、完全グラフ、安定結婚問題、対称グラフ、巡回セールスマン問題、中国人郵便配達問題、一筆書き、平面グラフ、伊理正夫、径、ペトリネット、マッチング (グラフ理論)、マトロイド、ネットワーク理論、ハミルトン路、ハミルトン閉路問題、ハイパーリンク、ハイパーグラフ、バス、ラムゼー理論、ラテン語、リード線、ループ量子重力理論、レオンハルト・オイラー、ワーシャル–フロイド法、パーコレーション、デッドロック、フローネットワーク、ファイルシステム、ニューラルネットワーク、ベイジアンネットワーク、ウェブページ、エッジ、オイラー路、カット (グラフ理論)、ガベージコレクション、クリーク (グラフ理論)、グラフ (データ構造)、グラフ同型、グラフ彩色、シュプリンガー・ジャパン、シュタイナー木、スモール・ワールド現象、サイエンス社、冪集合、写像、全域木、共立出版、元 (数学)、...、回路図、四色定理、矢印、秋山仁、空グラフ、素集合データ構造、独立集合、隣接行列、道 (グラフ理論)、頂点被覆問題、駅、路線、路線図、茨木俊秀、部分集合、閉路、閉路グラフ、鉄道、電気回路、集合、連結グラフ、Program Evaluation and Review Technique、World Wide Web、接点、根上生也、概念、次数 (グラフ理論)、次数直径問題、正則グラフ、朝倉書店、木 (数学)、有向非巡回グラフ、最大フロー最小カット定理、最大クリーク問題、最短経路問題、情報科学、意味ネットワーク、1736年、2部グラフ。 インデックスを展開 (39 もっと) »
名称のあるグラフのギャラリー
ラフ理論において名前が付いたグラフ（グラフ理論）の一覧を以下に示す。.
新しい！!: グラフ理論と名称のあるグラフのギャラリー · 続きを見る »
存在グラフ
存在グラフ（Existential graph）は、チャールズ・サンダース・パースが考案した、論理式を視覚的な図として表す記法、またはその図である。パースは1882年に初めて論理グラフについての論文を書き、1914年に死去するまでその手法の研究を続けた。.
新しい！!: グラフ理論と存在グラフ · 続きを見る »
完全グラフ
記載なし。
新しい！!: グラフ理論と完全グラフ · 続きを見る »
安定結婚問題
安定結婚問題（あんていけっこんもんだい、stable marriage problem）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。 安定結婚問題はn人の男性とk人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（stable matching）という。 下図に安定結婚問題の例題とその例題の解となる安定なマッチング、および、安定でないマッチングを示す。 画像:SMExample.JPG 「：」以下が各個人の希望リストである。点線はブロッキングペアを表している。 全ての例題について、安定マッチングは必ず存在する。それを見つける O(N2) 時間アルゴリズムが存在することも知られている（下を参照）。.
新しい！!: グラフ理論と安定結婚問題 · 続きを見る »
対称グラフ
数学のグラフ理論の分野において、あるグラフ G が対称グラフ（たいしょうぐらふ、）あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1—v1 および u2—v2 に対して、 であるような が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上（すなわち、方向を持つと考えられる辺の上）で推移的に作用することを言う。 そのようなグラフはしばしば1-弧推移的（1-arc-transitive）あるいは旗推移的（flag-transitive）とも呼ばれる。 定義に従い（u1 と u2 を無視することで）、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、a—b が d—c ではなく c—d へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。 したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する。しかしながら、次数が偶数である場合は、頂点推移的かつ辺推移的であるが、対称でないような連結グラフも存在する。そのようなグラフは（half-transitive）であると呼ばれる。最小の連結半推移グラフは、次数4で頂点数27のである。厄介なことに、学者の中には対称グラフという語を、弧推移グラフではなく、頂点推移的かつ辺推移的であるようなグラフに対して用いる人もいる。そのような定義では、上述の定義では除外されている半推移グラフを含むことになる。 距離推移グラフでは、隣接している頂点同士のペア（すなわち、距離が1だけ離れている頂点のペア）を考える代わりに、各々が同じ距離だけ離れているペアを考える。そのようなグラフは、定義より、自然に対称グラフとなる。 t-弧という語が、「 個の頂点からなる列で、その列において連続するどの二つの頂点も必ずグラフ上で隣接し、かつ繰り返し現れる頂点については必ず二段階以上離れているもの」に対して定義される。t-推移グラフとは、その自己同型群がt-弧の上では推移的に作用するが (t+1)-弧の上ではそのように作用しないグラフのことを言う。1-弧は単純に辺であるため、次数が3以上であるような全ての対称グラフには、t-推移的となるような t が必ず存在し、そのような t の値は対称グラフを分類する際に用いられる。例えば、立方体は2-推移的である。.
新しい！!: グラフ理論と対称グラフ · 続きを見る »
巡回セールスマン問題
巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。 巡回セールスマン問題（じゅんかいセールスマンもんだい、traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。.
新しい！!: グラフ理論と巡回セールスマン問題 · 続きを見る »
中国人郵便配達問題
中国人郵便配達問題（ちゅうごくじんゆうびんはいたつもんだい、）とは、グラフ理論における問題の一つであり、以下のように定義される。.
新しい！!: グラフ理論と中国人郵便配達問題 · 続きを見る »
一筆書き
六芒星の一筆書きの例 一筆書き（ひとふでがき）とは、広い意味では「筆記具を平面から一度も離さず線図形を描く」ことである。狭い意味では、これに加えて「同じ線を二度なぞらない（点で交差するのはかまわない）」という条件が加わる。筆記体のdは、前者の意味では一筆書きであるが、後者の意味では一筆書きではない。 以下は後者の狭い意味での一筆書きについて記す。 三角形「△」や四角形「□」は一筆書き可能だが、十字「+」は一筆書きできない。また、五芒星や白星「☆」、六芒星「✡」は一筆書き可能だが、アスタリスク「＊」は一筆書きができない。このように、一筆書きできる図形とできない図形がある。 「与えられた図形が一筆書き可能かどうか」という問題の例として、「ケーニヒスベルクの橋の問題」（Königsberger Brückenproblem）が知られている。なお、ケーニヒスベルクとは実際にあった場所の名前である。.
新しい！!: グラフ理論と一筆書き · 続きを見る »
平面グラフ
平面グラフ (plane graph) は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフのことである。平面グラフと同型なグラフのことを平面的グラフ (planar graph) という。 平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。 極小な非平面的グラフは、K3,3とK5。.
新しい！!: グラフ理論と平面グラフ · 続きを見る »
伊理正夫
伊理 正夫（いり まさお、1933年（昭和8年） - ）は、日本の数学者・工学者。東京大学名誉教授、元同大学工学部長・中央大学理工学研究所所長。工学博士（東京大学）。専門は数理工学、応用数学。.
新しい！!: グラフ理論と伊理正夫 · 続きを見る »
径
初等幾何学における図形の径（けい、diameter）は、その図形の差し渡しをいう。διάμετρος（「亙りの」+ 「大きさ」） に由来する。 円の直径は、その円の中心を通り、両端点がその円周上にある任意の線分であり、またその円の最長のでもある。球体の直径についても同様。 より現代的な用法では、任意の直径の（一意な）長さ自身も同じく「直径」と呼ばれる（一つの円に対して線分の意味での直径は無数にあるが、その何れも同じ長さを持つことに注意する。それゆえ（量化を伴わず）単に円の直径といった場合、ふつうは長さとしての意味である）。長さとして、直径は半径 (radius) の二倍に等しい。 平面上の凸図形に対して、その径は図形の両側から接する二本の平行線の間の最長距離として定義される（同様の最小距離は幅 (width) と呼ばれる）。径（および幅）はを用いて効果的に計算することができる。ルーローの三角形のような定幅図形では、任意の平行接線が同じ長さを持つから、径と幅は一致する。.
ペトリネット
ペトリネット ペトリネット（Petri net）とは、カール・アダム・ペトリが1962年に発表した離散分散システムを数学的に表現する手法である。モデリング言語としては分散システムを注釈付の有向2部グラフとして視覚的に表現する。.
新しい！!: グラフ理論とペトリネット · 続きを見る »
マッチング (グラフ理論)
ラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング、枝数が最大のものを最大マッチングという。また、グラフ上の全ての頂点が、マッチング中のいずれかの枝の端点になっているとき、そのマッチングを完全マッチングという。 極大マッチング、最大マッチングは必ず存在するが、完全マッチングは存在するとは限らない。（例: 奇数個頂点のグラフ）.
新しい！!: グラフ理論とマッチング (グラフ理論) · 続きを見る »
マトロイド
マトロイド(matroid)はある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。.
新しい！!: グラフ理論とマトロイド · 続きを見る »
ネットワーク理論
インターネットのネットワーク ネットワークの例 ネットワーク理論（ネットワークりろん）とは、通信、コンピュータ、生物、ソーシャルなどの複雑ネットワークを研究する分野。ネットワークは、ノードやエッジが属性（例：名前）を持つグラフとして定義される。数学のグラフ理論、物理学の統計力学、コンピュータサイエンスのデータマイニングと情報視覚化、統計からの推論モデリング、社会学の社会構造などの理論や手法が使われる。.
新しい！!: グラフ理論とネットワーク理論 · 続きを見る »
ハミルトン路
ハミルトン路とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。 与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP完全。与えられたグラフがハミルトングラフかどうか判定する問題については、ハミルトン閉路問題を参照のこと。.
新しい！!: グラフ理論とハミルトン路 · 続きを見る »
ハミルトン閉路問題
ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。.
新しい！!: グラフ理論とハミルトン閉路問題 · 続きを見る »
ハイパーリンク
ハイパーリンク（Hyperlink）とは、ハイパーテキストにおいて、複数の文書を結び付ける役割を担う「参照」である。ハイパーテキストの根幹をなす。単に「リンク」とも呼ばれる。 最もよく使われているであろうとされるリンクは、World Wide Web（WWW）におけるUniform Resource Locator（URL）によるものである。.
新しい！!: グラフ理論とハイパーリンク · 続きを見る »
ハイパーグラフ
ハイパーグラフの例: X.
新しい！!: グラフ理論とハイパーグラフ · 続きを見る »
バス
バス(bass,bath,bus,buss,bath) オムニバス (omnibus、乗り合い) の略.
ラムゼー理論
ラムゼー理論（ラムゼーりろん、Ramsey theory）は、一定の秩序がどのような条件の下で必ず現れるかを研究する数学の一分野である。名前はイギリスの数学者・哲学者であるフランク・ラムゼイ に因んでいる。ラムゼー理論の問題は、典型的には「ある構造がある性質を持つことを保証するには、その構造にはどのくらい元が必要か」という形のものである。.
新しい！!: グラフ理論とラムゼー理論 · 続きを見る »
ラテン語
ラテン語（ラテンご、lingua latina リングア・ラティーナ）は、インド・ヨーロッパ語族のイタリック語派の言語の一つ。ラテン・ファリスク語群。漢字表記は拉丁語・羅甸語で、拉語・羅語と略される。.
新しい！!: グラフ理論とラテン語 · 続きを見る »
リード線
リード線（リードせん、導線と同義）とは、電気回路において電源や電子部品などを電気的に接続するための電線の総称である。ビニール線、すずめっき線、エナメル線などが存在する。 リード線は、電気回路を構成する導体で、電子部品間で電気信号や電気エネルギーを伝える役割を果たす。あくまで回路内の配線の呼称であり、回路同士を結ぶものや大型の送電線などはリード線と呼ばれない。 回路図では、リード線は通常抽象化されて表されるが、実装においては実体のある物として配置される。超伝導が起こるような場合を除き、微小ながら電気抵抗を持つ。大電流が流れる回路では抵抗値が無視できなくなる。特に高周波回路では、リード線はリアクタンスを持つ電気素子として扱う事もある。配線方法を工夫する事により、リアクタンスの影響を軽減する事ができる。 Category:電子部品.
新しい！!: グラフ理論とリード線 · 続きを見る »
ループ量子重力理論
ループ量子重力理論（ループりょうしじゅうりょくりろん）は、時空（時間と空間）にそれ以上の分割不可能な最小単位が存在することを記述する理論である。超弦理論と並び、重力の古典論である一般相対性理論を量子化した量子重力理論の候補である。 同じく量子重力理論の候補である超弦理論は、時空は背景場として最初からそこに存在するものとして定義しており、理論自身のダイナミクスにより決定されているわけではない。それに対しループ量子重力理論は、一般相対論と同様に理論自身が時空そのものを決定している。(背景独立性).
新しい！!: グラフ理論とループ量子重力理論 · 続きを見る »
レオンハルト・オイラー
レオンハルト・オイラー（Leonhard Euler, 1707年4月15日 - 1783年9月18日）は、18世紀の数学者・天文学者（天体物理学者）。 18世紀の数学の中心となり、続く19世紀の厳密化・抽象化時代の礎を築いた 日本数学会編『岩波数学辞典 第4版』、岩波書店、2007年、項目「オイラー」より。ISBN 978-4-00-080309-0 C3541 。スイスのバーゼルに生まれ、現在のロシアのサンクトペテルブルクにて死去した。.
新しい！!: グラフ理論とレオンハルト・オイラー · 続きを見る »
ワーシャル–フロイド法
ワーシャル–フロイド法（Warshall–Floyd Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるとロバート・フロイドにちなむ（二人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド-ワーシャル法とも呼ばれる。.
新しい！!: グラフ理論とワーシャル–フロイド法 · 続きを見る »
パーコレーション
パーコレーション（percolation、浸透）とは、コーヒーの抽出機のパーコレーターのようにガソリンが気化して吹き出す現象。 元は自動車用語で、ガソリンがキャブレターに到達するまでに気化し、燃料パイプ内に気泡を生ずること。キャブレター内に燃料が染み出したり、ガソリンが気泡を生じているので、密度が減少して所要量を満たさずエンジンが停止するなどの不具合を生じることがある。エンジンが冷えるまで症状は回復しない。燃料噴射装置を採用している車両では、燃料供給装置内が加圧されているので起こりにくい。ブレーキ液のベーパーロック現象とは似て非なるものであるが、日本でも古くはベーパーロック現象と呼んでいたり、アメリカではパーコレーションのことをベーパーロックと呼ぶ人もいるため、間違いとまでは言いにくい。 また数理工学の分野において、ランダム系を統計的に考察するパーコレーション理論 (percolation theory) が注目されている。 物性物理学・統計力学においては、ランダム系における電気伝導やスピングラス等における秩序の拡散などの現象を記述する理論であり、その応用として画像処理等が考えられる。「パーコレーション網状組織」といった用語も存在する。.
新しい！!: グラフ理論とパーコレーション · 続きを見る »
デッドロック
デッドロック (英: deadlock) とは、特に計算機科学において、2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまうことを言う。 また、合弁契約書などにおいてパートナーと利害関係がぶつかるような問題が生じた場合の解決方法を定めた条項を「デッドロック条項（Deadlock Clause）」と言う。 英語ではもともと行き詰まりの意味である。.
新しい！!: グラフ理論とデッドロック · 続きを見る »
フローネットワーク
フローネットワーク（Flow network）は、グラフ理論における重み付き有向グラフの一種であり、各枝に容量（capacity）を設定し、各枝をフロー（flow）が流れる。各枝のフローはその容量を超えることはない。オペレーションズ・リサーチでは、重み付きグラフをネットワークと呼び、頂点をノード、枝をアークと呼ぶ。フローが満足すべき制約条件として、1つのノードに流入するフローとそのノードから流出するフローは常に等しい。ただし、始点（source）と終点（sink）では、その限りではない。このネットワークは、例えば道路網の交通量、パイプを流れる液体、電気回路を流れる電流、その他の何らかのネットワーク上を移動するものをモデル化するのに適している。.
新しい！!: グラフ理論とフローネットワーク · 続きを見る »
ファイルシステム
ファイルシステムは、コンピュータのリソースを操作するための、オペレーティングシステム (OS) が持つ機能の一つ。ファイルとは、主に補助記憶装置に格納されたデータを指すが、デバイスやプロセス、カーネル内の情報といったものもファイルとして提供するファイルシステムもある。 より正確に定義すれば、ファイルシステムは抽象データ型の集まりであり、ストレージ、階層構造、データの操作/アクセス/検索のために実装されたものである。ファイルシステムを特殊用途のデータベース管理システム (DBMS) と見なせるかどうかは議論があるが、ファイルシステムとデータベース管理システムには多くの共通点がある。.
新しい！!: グラフ理論とファイルシステム · 続きを見る »
ニューラルネットワーク
ニューラルネットワーク（神経回路網、neural network、略称: NN）は、脳機能に見られるいくつかの特性を計算機上のシミュレーションによって表現することを目指した数学モデルである。研究の源流は生体の脳のモデル化であるが、神経科学の知見の改定などにより次第に脳モデルとは乖離が著しくなり、生物学や神経科学との区別のため、人工ニューラルネットワーク（artificial neural network、ANN）とも呼ばれる。.
新しい！!: グラフ理論とニューラルネットワーク · 続きを見る »
ベイジアンネットワーク
ベイジアンネットワーク（Bayesian network）は、因果関係を確率により記述するグラフィカルモデルの1つで、複雑な因果関係の推論を有向非巡回グラフ構造により表すとともに、個々の変数の関係を条件つき確率で表す確率推論のモデルである。ネットワークとは重み付けグラフのこと。 ジューディア・パールが1985年に命名した。ジューディア・パールはこの研究の功績によりチューリング賞を受賞した。 人工知能の分野では、ベイジアンネットワークを確率推論アルゴリズムとして1980年頃から研究が進められ、既に長い研究と実用化の歴史がある。.
新しい！!: グラフ理論とベイジアンネットワーク · 続きを見る »
ウェブページ
ウェブページ (Web page, webpage) は、ウェブ上にあり、ウェブブラウザで閲覧可能な、ページ単位の文書のこと。ホームページと表記することもあるが、誤用であるという主張もある(詳しくはホームページの項を参照）。.
新しい！!: グラフ理論とウェブページ · 続きを見る »
エッジ
ッジ (Edge).
オイラー路
イラー路（オイラーろ、Eulerian trail）とは、グラフの全ての辺をちょうど1度だけ通る路のこと。また全ての辺をちょうど1度だけ通る閉路は、オイラー閉路（オイラーへいろ、Euler circuit）という。これらの名称は1736年にこれらを含むグラフの特徴づけを与えたレオンハルト・オイラーにちなむ。 グラフの辺をすべて通るようなオイラー閉路を持つグラフのことをオイラーグラフ（Eulerian graph）という。またグラフの辺をすべて通るような、閉路でないオイラー路を持つグラフのことを準オイラーグラフという。.
新しい！!: グラフ理論とオイラー路 · 続きを見る »
カット (グラフ理論)
ラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（Cut）とよぶ。このとき、ある辺 (u,v) \in E の端点が u \in S かつ v \in T（有向グラフの場合 u \in T でかつ v \in S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。 カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。 頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、 劣モジュラ関数、かつ、正モジュラ関数である。.
新しい！!: グラフ理論とカット (グラフ理論) · 続きを見る »
ガベージコレクション
ベージコレクション（garbage collection; GC）とは、プログラムが動的に確保したメモリ領域のうち、不要になった領域を自動的に解放する機能である。「ガベージコレクション」を直訳すれば「ゴミ集め」「ごみ拾い」となる。1959年ごろ、LISPにおける問題を解決するためジョン・マッカーシーによって発明された。 メモリの断片化を解消する機能はコンパクションと呼ばれ、実現方法によってはガベージコレクションと共にコンパクションも行う仕組みになっている。そのためコンパクションを含めてガベージコレクションと呼ぶ場合もあるが、厳密には区別される。 また、ガベージコレクションを行う主体はガベージコレクタと呼ばれる。ガベージコレクタはタスクやスレッドとして実装される場合が多い。 参照カウント方式のガベージコレクションは通常煩雑なコーディングを必要とするが、それを必要なく実装したライブラリとしがある。.
新しい！!: グラフ理論とガベージコレクション · 続きを見る »
クリーク (グラフ理論)
K5 完全グラフ。部分グラフがこのようになっている場合、その部分グラフの頂点群は大きさ5のクリークを形成している。 6個の頂点と7本の辺から成るグラフ。このグラフでは大きさ3の唯一のクリークが 1, 2, 5 である。 グラフ理論において、無向グラフ G.
新しい！!: グラフ理論とクリーク (グラフ理論) · 続きを見る »
グラフ (データ構造)
6個の頂点と7本の枝からなるラベル付きグラフ グラフ（英: Graph）とは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成される抽象データ型、and・orその実装である具象データ型である。グラフ理論によるグラフの実装であり、同理論にもとづく豊富なアルゴリズムの基盤である。 グラフは G.
新しい！!: グラフ理論とグラフ (データ構造) · 続きを見る »
グラフ同型
ラフ同型（ぐらふどうけい）とはグラフ理論における概念の一つである。.
新しい！!: グラフ理論とグラフ同型 · 続きを見る »
グラフ彩色
3色に頂点彩色（最適彩色）されたグラフ。ピーターセングラフの彩色数は3である。 グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。.
新しい！!: グラフ理論とグラフ彩色 · 続きを見る »
シュプリンガー・ジャパン
ュプリンガー・ジャパン（しゅぷりんがー・じゃぱん・Springer Japan）は、ドイツのSTM（科学・技術・医学）出版社であるシュプリンガー・サイエンス・アンド・ビジネス・メディアの日本法人である。この親会社が出版する書籍・ジャーナルを日本国内で出版している。 同社は、以前にはそれらの日本語翻訳書や和書の出版も行っていたが、2012年に権利を丸善へと譲渡して和書事業から撤退した。これに拠って、シュプリンガー・ジャパンから出版されていた和書は丸善から順次(再)刊行されている。 2015年5月、シュプリンガー・サイエンス+ビジネスメディアとマクミラン・サイエンス・アンド・エデュケーションの大半の事業の合併が、欧州連合や米国司法省などの主要な公正競争監視機関により承認された。新会社の名称は「シュプリンガー・ネイチャー（Springer Nature）」。.
新しい！!: グラフ理論とシュプリンガー・ジャパン · 続きを見る »
シュタイナー木
ュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG.
新しい！!: グラフ理論とシュタイナー木 · 続きを見る »
スモール・ワールド現象
モール・ワールド現象（スモールワールドげんしょう、small world phenomenon, small world effect）は、知り合い関係を芋づる式にたどっていけば比較的簡単に世界中の誰にでも行き着くという仮説である。あえて日本語にすれば（広いようで）「世間は狭い」現象である。 この仮説は社会心理学者スタンレー・ミルグラムが1967年に行ったスモールワールド実験 (small world experiment) で検証され、その後この仮説をもとに六次の隔たりという有名なフレーズが生まれた。この実験ではアメリカ合衆国国民から2人ずつの組を無作為に抽出し、その2人がつながっている場合には、平均すると6人の知り合いを介していることを求めた。 しかし、30年以上たった現在でも、均質化されていない（heterogeneousな）ソーシャルネットワークの間においてはどうなのか（前記「世界中の誰にでも」の類）、いまだに決着がついていない。その種の実験は、ミルグラムの論文以来ほとんど行われてこなかった。.
新しい！!: グラフ理論とスモール・ワールド現象 · 続きを見る »
サイエンス社
株式会社サイエンス社（サイエンスしゃ、英称:SAIENSU-SHA Co.,Ltd.）は、東京都渋谷区千駄ヶ谷にある日本の出版社である。.
新しい！!: グラフ理論とサイエンス社 · 続きを見る »
冪集合
冪集合（べきしゅうごう、power set）とは、数学において、与えられた集合から、その部分集合の全体として新たに作り出される集合のことである。べきは冪乗の冪（べき）と同じもので、冪集合と書くのが正確だが、一部分をとった略字として巾集合とも書かれる。 集合と呼ぶべき対象を公理的に構成的に与える公理的集合論では、集合から作った冪集合が集合と呼ばれるべきもののうちにあることを公理の一つ（冪集合公理）としてしばしば提示する。.
写像
写像（しゃぞう、mapping, map）とは、二つの集合が与えられたときに、一方の集合の各元に対し、他方の集合のただひとつの元を指定して結びつける対応のことである。函数（関数）、変換、作用素、射などが写像の同義語として用いられることもある。 ブルバキに見られるように、写像は集合とともに現代数学の基礎となる道具の一つである。現代的な立場では、「写像」と（一価の）「函数」は論理的におなじ概念を表すものと理解されているが、歴史的には「函数」の語は解析学に出自を持つものであり、一部には必ずしも写像でないものも函数の名の下におなじ範疇に扱われる（多価函数参照）。文献によっては「数の集合（大抵の場合実数体 または複素数体 の部分集合）を終域に持つ写像」をして特に「函数」と呼び、「写像」はより一般の場合に用いる。函数、二項関係、対応の各項も参照のこと。.
全域木
4×4のグリッドグラフにおける全域木の一例 全域木（ぜんいきぎ、Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、グラフ理論において、以下のように定義される木のことである。 つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。.
共立出版
共立出版株式会社（きょうりつしゅっぱん）は、理工系の専門書を中心に刊行している出版社。自然科学書協会、日本理学書総目録刊行会に加盟している。大学の教科書としてもよく使用され、大学生協との取引も多い。.
新しい！!: グラフ理論と共立出版 · 続きを見る »
元 (数学)
数学において元（げん、element）とは、集合を構成する個々の数学的対象のことである。ジュゼッペ・ペアノの導入した記法に従えば、対象 が集合 の元であることを と書き表す。このとき対象 が集合 に属する（ぞくする、membership）、あるいは集合 は対象 を含むとも言う。 「属する」という二項関係は、数学的対象と集合（あるいは一般にクラス）との間に定まる非対称な関係（帰属関係）である。外延性の公理により、集合はそれに属する全ての数学的対象を指定することで特徴づけられる。 通常用いられる においては基礎の公理が述べるところによって帰属関係は整礎、すなわち任意の集合は自身を元として含むことはない（帰属関係は反対称関係である）。しかし、基礎の公理の代わりにを置くではそのような制約を受けないが存在し得る。 帰属関係は推移的でない。これは集合の包含関係がそうであることと対照的である。.
新しい！!: グラフ理論と元 (数学) · 続きを見る »
回路図
回路図（かいろず）とは電子回路、空気圧機器、油圧機器などの回路を記述するために用いられる図のことである。実体配線図と異なり、回路図での位置と実際に配置する場所は無関係であり、一種のグラフである。.
四色定理
四色定理（よんしょくていり／ししょくていり、）とは、厳密ではないが日常的な直感で説明すると「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分だ」という定理である。.
新しい！!: グラフ理論と四色定理 · 続きを見る »
矢印
印（やじるし）とは主に方向を指し示すのに使われる記号。 代表的なものに←、↑、→、↓があり、それぞれ左、上、右、下を表す。 信号機で使われている矢印 矢印という名前は読んで字のごとく、矢を表している。これは矢の、一度特定の方向に放たれたら地面に落ちるまで真っ直ぐに進む性質を想起させるため、世界中で一般的に使われている。.
秋山仁
秋山 仁（あきやま じん、1946年10月12日 - ）は、日本の数学者。東海大学名誉教授、東京理科大学特任副学長 兼 理数教育研究センター長。専攻はグラフ理論、離散幾何学。理学博士。東京都武蔵野市出身。.
空グラフ
ラフ（英: null graph）は、数学のグラフ理論において、位数0のグラフ、または辺のないグラフ (edgeless graph) を意味する（後者は empty graph とも呼ぶ）。.
新しい！!: グラフ理論と空グラフ · 続きを見る »
素集合データ構造
素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。.
新しい！!: グラフ理論と素集合データ構造 · 続きを見る »
独立集合
24個の頂点からなるこのグラフで、青い9個の頂点の集合が極大独立集合である。 グラフ理論における独立集合（どくりつしゅうごう、independent set）または安定集合（stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。 極大独立集合 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 与えられたグラフが特定の大きさの独立集合を持つかどうかを判定する問題を独立集合問題と呼ぶ。これは計算上、そのグラフが特定の大きさのクリークを持つかどうかの判定と等価である。このことは、グラフが大きさ k の独立集合を持つとき、その補グラフ（頂点は同じだが、辺が相補的なグラフ）は大きさ k のクリークを持つという事実から導かれる。独立集合（およびクリーク）の決定問題は、NP完全問題であることが知られている。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。.
新しい！!: グラフ理論と独立集合 · 続きを見る »
隣接行列
隣接行列（りんせつぎょうれつ、adjacency matrix）とは、における基本的な概念で、グラフの頂点と頂点の隣接関係を表わす正方行列である。 頂点集合を とする有限無向グラフ に対して、その隣接行列 とは（頂点集合によって添字づけられた） 次正方行列であって、その 成分 は頂点 と頂点 を結ぶ枝の数で定義される。これによりグラフ の固有多項式やスペクトルがそれぞれ隣接行列 の固有多項式やスペクトルとして定義される。これらはグラフの不変量である（隣接行列そのものは頂点集合上の置換を除いてしか定まらない）。 有向グラフの場合、 から に向かう枝があるときのみ 成分を 1 に、そうでないとき 成分を 0 にする。また、枝に重みがついているグラフの場合は、 成分を重みとする。.
新しい！!: グラフ理論と隣接行列 · 続きを見る »
道 (グラフ理論)
有向閉道の例。矢印がなければ単なる閉道である。青い頂点は2度通るので、単純な閉道（すなわち閉路）ではない。 グラフ理論において、グラフの道（みち）またはパス（path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al.
新しい！!: グラフ理論と道 (グラフ理論) · 続きを見る »
頂点被覆問題
頂点被覆問題（ちょうてんひふくもんだい）は計算複雑性理論における問題の一つであり、 NP完全に属する問題の内のひとつ。.
新しい！!: グラフ理論と頂点被覆問題 · 続きを見る »
駅
駅（えき、うまや）.
路線
路線（ろせん）は、交通機関が通過する、出発地点と目的地点を結ぶ線。鉄道路線、バス路線、航空路線、航路など。 陸上交通では、道路や鉄道など実体がある施設の上を運行する。航空や海運では、何もない空中や水面を運航するため、同じ「路線」であっても、気象状態などにより、実際に通過する線は同じとは限らない。 比喩的に、団体や組織など（特に政党や政府）の活動・運営の基本方針も意味する。.
路線図
路線図（ろせんず）とは、鉄道・バスや道路、送電線等の路線・施設（停留所等）の接続・配置関係を相対的に示した図表である。ここでは鉄道・路線バスのものを中心に詳述する。.
茨木俊秀
茨木 俊秀（いばらき としひで、1940年9月29日『読売年鑑 2016年版』（読売新聞東京本社、2016年）p.252 - ）は、京都情報大学院大学の学長である。兵庫県出身。.
新しい！!: グラフ理論と茨木俊秀 · 続きを見る »
部分集合
集合 A が集合 B の部分集合（ぶぶんしゅうごう、subset; 下位集合）であるとは、A が B の一部（あるいは全部）の要素だけからなることである。A が B の一部分であるという意味で部分集合という。二つの集合の一方が他方の部分集合であるとき、この二つの集合の間に包含関係があるという。.
新しい！!: グラフ理論と部分集合 · 続きを見る »
閉路
有向閉路の例。青い頂点を2度通るので単純閉路ではない。 閉路（へいろ、cycle, circuit, closed walk）あるいは閉道（へいどう、closed path）とは、始点と終点が同じ路のこと。すなわち、出発点に戻るような辿り方のことである。グラフ理論や位相幾何学において用いられる。 単純閉路（たんじゅんへいろ、simple cycle）とは、自分自身と交差していない閉路のこと。グラフの単純閉路であればいかなる頂点も一度しか現れない。 閉路ならば同じところを行ったり来たりして辿ってもよく、同じところを繰り返し通らない閉路のことを閉道という。 n個の相異なる頂点vi（i.
閉路グラフ
長さ6の閉路グラフ 閉路グラフ（へいろグラフ、cycle graph）は、グラフ理論において1つの閉路（正確には閉道）から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪を形成しているグラフである。n個の辺による閉路グラフを Cn と表記する。Cn においては、辺と頂点の数は等しく、各頂点の次数は常に2である。つまり、各頂点は常に2つの辺と接合している。.
新しい！!: グラフ理論と閉路グラフ · 続きを見る »
鉄道
鉄道（てつどう、railway railroad）とは、等間隔に設置された2本の鉄製の軌条（レール）またはそれに代わる物を案内路として車輪を有する車両が走行する交通機関である。線路・停車場などの施設、旅客や貨物を輸送する列車、運行管理や信号保安まで様々な要素で構成される一連の体系である。 広い意味では、レール、案内軌条などの案内路に誘導されて走行する車両を用いた交通機関を指し、懸垂式・跨座式のモノレール、案内軌条式のAGT（新交通システム）、鋼索鉄道（ケーブルカー）、浮上式鉄道を含む。日本では鉄道事業法の許可、または、軌道法の特許を得て敷設される。トロリーバス（無軌条電車）は、架線が張られたルートを集電装置（トロリー）により集電した電気を動力として走行するバスであるが、鉄道事業法に基づく鉄道、または、軌道法上の「軌道に準ずる」軌道として扱われる。ロープウェイも鉄道事業法、または、軌道法の対象であるが、索道という扱いとなる。 なお、本項では鉄製レールの案内路を有する鉄道について解説する。.
電気回路
電気回路（でんきかいろ、electric(al) circuit）は、抵抗器（抵抗）、インダクタ、コンデンサ、スイッチなどの電気的素子が電気伝導体でつながった電流のループ（回路）である。 電気回路は、電流の流れのための閉ループを持っていて、2つ以上の電気的素子が接続されている。 「回路」の語義的にはループになっているものだけであり、また電流は基本的にはその性質として、ループになっていなければ流れないものであるが、アンテナやアースのように開放端になっている部分も通例として含めている。対象が電子工学的（弱電）であるものは電子回路と言う。 例外的な分野の例ではあるが、主に数ギガヘルツの電磁波（電波）を伝播させる給電線である導波管をコンポーネント単位で、加工・細工するなどして、中空の導波管内を伝播する電磁波に直接作用させる形で構成した電気回路を立体回路と言う。これらは、基本的にループを構成せず、電気伝導体を介さない上記の電気回路の概念とは少し異なるものだが、電気回路の延長線上としてマイクロ波などの高周波領域であつかわれている。 導波管は金属の管であり、加工により通常の電気回路にあるような電気的素子である容量性（コンデンサ）、誘導性（インダクタ）、短絡（ショート）、抵抗減衰、分岐などを高周波領域で実現することが出来る。 これらは衛星通信やマイクロ波加熱、プラズマ生成など用途に応じて高出力（電力）で、かつ高周波の無線電波分野で用いられ、立体回路が構成される導波管は主に中空の方形導波管が多い。.
新しい！!: グラフ理論と電気回路 · 続きを見る »
集合
数学における集合 (しゅうごう、set, ensemble, Menge) とは、大雑把に言えばいくつかの「もの」からなる「集まり」である。集合を構成する個々の「もの」のことを元 (げん、; 要素) という。 集合は、集合論のみならず現代数学全体における最も基本的な概念の一つであり、現代数学のほとんどが集合と写像の言葉で書かれていると言ってよい。 慣例的に、ある種の集合が系 (けい、) や族 (ぞく、) などと呼ばれることもある。実際には、これらの呼び名に本質的な違いはないが細かなニュアンスの違いを含むと考えられている。たとえば、方程式系（「相互に連立する」方程式の集合）、集合族（「一定の規則に基づく」集合の集合）、加法族（「加法的な性質を持つ」集合族）など。.
連結グラフ
連結グラフ（れんけつグラフ, connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。.
新しい！!: グラフ理論と連結グラフ · 続きを見る »
Program Evaluation and Review Technique
5つのマイルストーン（10から50）と6つの作業（AからF）がある7カ月間のプロジェクトのPERT図 Program Evaluation and Review Technique（プログラム・エバリューション・アンド・レビュー・テクニック、PERT）とは、プロジェクトマネジメントのモデルの一種であり、プロジェクトの完遂までに必要なタスクを分析する手法である。Project Evaluation and Review Techniqueとも。.
新しい！!: グラフ理論とProgram Evaluation and Review Technique · 続きを見る »
World Wide Web
World Wide Web（ワールド・ワイド・ウェブ、略名：WWW）とは、インターネット上で提供されるハイパーテキストシステム。Web、ウェブ、W3（ダブリュー スリー）とも呼ばれる。俗には「インターネット」という表現がワールド・ワイド・ウェブを指す場合もある。.
新しい！!: グラフ理論とWorld Wide Web · 続きを見る »
接点
接点は、.
根上生也
根上 生也（ねがみ せいや、1957年 - ）は日本の数学者（理学博士）。横浜国立大学大学院環境情報研究院教授、理工学部数理科学EP担当。専門は、位相幾何学的グラフ理論、離散数学、トポロジー、数学教育。 東京工業大学理学部数学科卒業。同大学院理工学研究科情報科学博士課程中退。東京工業大学助手、横浜国立大学助教授を経て現職。東工大における指導教官は本間龍雄。 日本における位相幾何学的グラフ理論のパイオニアである。「根上多項式」や「平面被覆予想」の提唱者として有名。 2005年4月から9月まで、フジテレビで放送された教育番組『ガチャガチャポン!』にて「数学探偵セイヤ」として出演した。 2008年には、映画『容疑者Xの献身』の監修（数学）をした。.
新しい！!: グラフ理論と根上生也 · 続きを見る »
概念
概念（がいねん、哲学では仏: notion、独: Begriffというが、日常的に仏: concept、独: Konzeptという。コンセプトは前記フランス語から由来している）は、命題の要素となる項（Terminus）が表すものであり、言い換えれば、それが言語で表現された場合に名辞（Terminus）となるものが概念である。 事象に対して、抽象化・ 普遍化してとらえた、思考の基礎となる基本的な形態として、脳の機能によってとらえたもの。.
次数 (グラフ理論)
各頂点に次数を記したグラフ グラフ理論における次数（じすう、degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる。頂点 v の次数を \deg(v) と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。.
新しい！!: グラフ理論と次数 (グラフ理論) · 続きを見る »
次数直径問題
ラフ理論において次数直径問題とは、最大次数がdで直径がkのグラフのうち頂点数が最大となるグラフGを見つけよ、というものだ。Gの頂点数はムーア・バウンドによって上から抑えられる。1n_ とする。 n_\leq M_ となるM_はムーアバウンドと呼ばれ以下のようになる。 ムーアバウンドに到達するグラフは非常に少ないことが示されている。M_の漸近的な振る舞いは M_.
新しい！!: グラフ理論と次数直径問題 · 続きを見る »
正則グラフ
正則グラフ（せいそくグラフ、regular graph）は、グラフ理論において、各頂点の隣接する頂点数が全て同じであるようなグラフである。すなわち、全ての頂点の次数が等しい。頂点の次数が k の正則グラフを 「k-正則グラフ」または「次数 k の正則グラフ」と呼ぶ。 次数2までの正則グラフの分類は容易である。0-正則グラフは連結されていない頂点で構成され、1-正則グラフは連結されていない辺で構成され、2-正則グラフは連結されていない閉路で構成される。 3-正則グラフは立方体グラフとも呼ばれる。 正則グラフのうち、隣接する2つの頂点に共通する隣接点が常に同じ l 個で、隣接しない2つの頂点に共通する隣接点が常に同じ n 個となっているものを強正則グラフという。正則だが強正則でない最小のグラフは、6頂点の閉路グラフかつ循環グラフである。 完全グラフ K_m は任意の m について強正則である。 クリスピン・ナッシュ＝ウィリアムズの定理によれば、2k+1 個の頂点から成る k-正則グラフには必ずハミルトン路がある。 ファイル:0-regulární graf na 6 vrcholech.png|0-正則グラフ File:1-regulární graf na 6 vrcholech.svg|1-正則グラフ File:2-regulární graf na 6 vrcholech.svg|2-正則グラフ File:3-regular graph2.svg|3-正則グラフ.
新しい！!: グラフ理論と正則グラフ · 続きを見る »
朝倉書店
朝倉書店（あさくらしょてん）は、日本の出版社。 1929年（昭和4年）創業の賢文館が前身で、1944年（昭和19年）に株式会社朝倉書店設立。創業者は同文館出身の朝倉鑛造。 理学・工学・医学・農学・人文科学・家政学などの学術専門書および理工系の大学教科書を出版。.
新しい！!: グラフ理論と朝倉書店 · 続きを見る »
木 (数学)
数学、特にグラフ理論の分野における木（き、tree）とは、連結で閉路を持たない(無向)グラフである。有向グラフについての木（有向木）についても論じられるが、当記事では専ら無向木を扱う。 閉路を持たない（連結であるとは限らない）無向グラフを森（もり、forest）という。木は明らかに森である。 なお、閉路を持たない有向グラフは有向非巡回グラフである。有向木は有向非巡回グラフでもあるが、有向非巡回グラフは必ずしも有向木とは限らない。 コンピュータ上での木の扱いについては、木構造 (データ構造) を参照。 画像:Tree-sample1.png.
新しい！!: グラフ理論と木 (数学) · 続きを見る »
有向非巡回グラフ
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフの事。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶと polytree と呼ばれる特殊な有向非巡回グラフを作ることが出来る。しかしながら、無向非巡回グラフ（森）に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフは acyclic orientation があるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graph と呼ぶよりも acyclic directed graph と呼ぶ方が正確である。 なお、有向非巡回グラフをプロトコルとした仮想通貨に、BYTEBALL、IOTAがある。.
新しい！!: グラフ理論と有向非巡回グラフ · 続きを見る »
最大フロー最小カット定理
最大フロー最小カット定理（さいだいフローさいしょうカットていり、Max-flow min-cut theorem）は、フローネットワークにおいて最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。.
新しい！!: グラフ理論と最大フロー最小カット定理 · 続きを見る »
最大クリーク問題
最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。 この問題は、補グラフに対する最大独立集合問題と等価である。 近似アルゴリズムについても研究されているが、グラフの頂点数を とするとき、近似度 が達成されているのみである。また、P.
新しい！!: グラフ理論と最大クリーク問題 · 続きを見る »
最短経路問題
ラフ理論における最短経路問題（さいたんけいろもんだい、shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。.
新しい！!: グラフ理論と最短経路問題 · 続きを見る »
情報科学
情報科学という語は日本語では多義的に用いられている。.
新しい！!: グラフ理論と情報科学 · 続きを見る »
意味ネットワーク
意味ネットワーク（いみねっとわーく、, ）は人間の記憶の一種である意味記憶の構造を表すためのモデルである。 概念の間の意味関係を表現するネットワークである。知識表現でよく利用される。概念を表す節と、概念の意味関係を表す辺からなる、有向グラフまたは無向グラフである。.
新しい！!: グラフ理論と意味ネットワーク · 続きを見る »
1736年
記載なし。
新しい！!: グラフ理論と1736年 · 続きを見る »
2部グラフ
循環の無い2部グラフの例 完全2部グラフ 数学、とくにグラフ理論における2部グラフ（にぶぐらふ、bipartite graph）は、頂点集合を二つの部分集合に分割して各集合内の頂点同士の間には辺が無いようにできるグラフのことである。このような頂点の集合を独立集合といい、より一般にn個の独立頂点集合に分割可能なグラフのことをn部グラフ (n-partite graph) という。 完全2部グラフは、二つの頂点集合V1, V2に分割したとき、V1同士・V2同士の頂点間には辺が存在しないが、V1とV2間の任意の2点間に辺が存在するグラフのことである。m頂点の頂点集合とn頂点の頂点集合に分割されるような完全2部グラフのことをKm, nとかく。 隣り合った頂点同士を異なる色で塗ることを（頂点）彩色という。よって、n部グラフはn点彩色可能なグラフである。同様に、隣り合った辺同士を異なる色で塗ることを辺彩色という。 二部グラフの辺集合Mがマッチングであるとは、Mに属するどの2辺も隣接していないと言うことである。グラフGの最大マッチングとは、GのマッチングMのうち、辺の数が最大のものである。また、全ての頂点を含むマッチングのことを完全マッチングという。.
新しい！!: グラフ理論と2部グラフ · 続きを見る »
