頂点カバー問題がNP完全であるということ その３

　ソチオリンピックでの日本選手の活躍に心励まされる今日この頃。いくら私でも、さすがに少しがんばろうかなという気にもなってきました。どこまで続くか分からないというところが私らしいところですが。

　

さて、前回（頂点カバー問題がNP完全であるということ　その２）は、3SAT∝VCを証明するために、3SATの問題をVCの問題に翻訳するということをやりました。今回は、この、（リテラルの集合Uと節集合Cで表される）3SATの問題が、（グラフG=(V,E)といくつの頂点を選ぶかを表す数Kで表される）VCの問題と同等ということをこれから二回に分けて証明していきます。

　

【Kについて】
    まず、VCの問題におけるノードの集合W∈V（本来的にはWはV'と書きたいところですが、以下紛らわしいのでWとします）が|W|<Kを満たす頂点カバーだったとします。

　

①　前回のリテラルui∈U (1≦i≦n)を変換した部分グラフ Ti={Vi,Ei) について注目すると、部分グラフTiのノードの集合Viのどちらかのノードが含まれていないといけませんので、ノード集合Wとノード集合∪Viの共通部分（積集合）には少なくてもn個のノードが含まれています。

　
②　同様に、前回の節cj∈C(1≦j≦m)を変換した部分グラフSj={V'j,E'j}のうち、少なくても2個のノードがWに含まれなければなりませんので、ノード集合Wとノード集合∪V'jの積集合には少なくても2m個のノードが含まれます。

　

　|W|=Kでは、前回K=n+2mと定義しました。したがって、∪Viからはちょうどn個、∪V'jからはちょうど2m個のノードがWに含まれていることが分かります。

　
（※2014年5月7日　ノード集合Wとノード集合∪V'jの積集合のノードの数をｍ個と説明していましたが、正しくは2mこの間違いです。お詫びして訂正いたします）　

【VCの問題が3SATを満たしているか】
　ところで、いま3SATの問題におけるリテラルの集合Uの真理関数t:U→{T,F}を次のように定義する事とします。

　

　　　　

　　　　　　　　　　　　                                 
　ここで、Cj∈Cとしたとき、上記の真理関数tがCjを充足しているかどうかについて考えます。

　

　いま、前回の手順2で次のように定義しました。

　

　　　　 Sj={V'j,E'j}において
　　　　　　
　　　　　　V'j={　a1[j],　a2[j],　a3[j]　},
　　　　　　E'j={　{a1[j], a2[j]},　 {a2[j], a3[j]}, 　{a3[j], a1[j]}　}

　　　　　　(a1[j]∈Vかつa2[j]∈Vかつa3[j]∈V)

　

　手順4では、すべてのcj∈Cについて、cj={xj,yj,zj}と節を表すとき
　　　　　　枝の部分集合を
　　　　　　　
　　　　　　　E"j={　{a1[j], xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
と表すことにし、最後に、こうしたときグラフGの枝の集合Eを

　　　　　　

　　　 （※2014年5月7日　上の図表の式と同じくE'jおよびE''jの和集合の添え字が
                        mでは無くnになっていました。お詫びして訂正いたします）

また、ここでK=n+2mと定義する

　　　　　　　　

と定義しました。

　

　上記【Kについて】②においても記述していますが、WにはV'jのノードのうちすくなくても二つが含まれます。しかし、K=n+2mと定義されていますから、E''を満たすためには、最低でももう一つのノードが、手順4のcj={xj,yj,zj}のいずれかのノードでなければならず、したがって、cjに含まれる頂点はVCの問題を満たす部分集合Wであるということを満たさなければならないという事が分かります。

　今回はここまでにしましょう。次回は、3SATの問題が逆にVCをみたしているかを考えてみます。

　

葛西選手の妹さまの御快癒と日本選手団のみなさまのご活躍を祈念いたしまして。

頂点カバー問題がNP完全であるということ その２

疲れていますか？私は疲れています。いわばご乱心です。なにがと聞かれても困りますが。そういうわけで今回は、寒さ厳しい折ということもあってよけいに寒くなるようなそういう無駄な部分を省こうと思います。ここまで、いろいろ意味を問われても困ります。

　

前回、頂点カバー問題（以下VCと略す）がクラスＮＰであると言うことをお話ししました。VCがＮＰ完全であると言うためには、ＮＰ完全であるという問題、今回はそれが3SATとなりますが、それと同等な問題である（SAT∝VCと表記する）ということを証明すれば良い訳です。

　

大まかな方法論としては、3SATの問題（「３SAT　その１」などを参照下さい）をVCの問題に翻訳します。

　

3SATはすべてのリテラル（ここではブール変数と同じと考えても可）の集合U={u1,u2,…,un}と、各節の要素の数が3つのブール変数に固定された節の集合C={c1,c2,…,cm}で一般的に表されます。

一方、VCについては、ノードの集合をV、枝の集合をEとしたとき一般的なグラフGをG={V,E}と表しすことにし、これがVCとして成立するノードの数をK（K≦｜V｜）と定義することにします。

3SATの問題をVCに翻訳するためにもう一つ、グラフＧをいろいろな部分集合の和であると定義しておきます。

　

このような準備をしてから、実際の翻訳作業に入ります。

　

　

　

　手順1.　3SATのリテラルui∈Uを部分グラフで表すことを考える

　　　　　そのような部分グラフをTi={Vi,Ei}と表すとき、Vi={ui,￢ui},Ei={{ui,￢ui}}とする

　

　　　　　このようにした場合、G={V,E}の頂点カバーであるようなノードの集合V'には
　　　　　uiか￢uiのどちらかが必ず含まれることになる　　　

　

　手順2．次に3SATの節cj∈Cについて同様のことを考え、そのような部分グラフを
　　　　 Sj={V'j,E'j}と表すこととすると、V'jとE'j次のように考えられる
　　　　　　
　　　　　　V'j={　a1[j],　a2[j],　a3[j]　},
　　　　　　E'j={　{a1[j], a2[j]},　 {a2[j], a3[j]}, 　{a3[j], a1[j]}　}

　

　　　　　ここで、a1[j], a2[j], a3[j]は新しく導入されたノードの表記ではあるが、
　　　　　当然ながら、a1[j]∈Vかつa２[j]∈Vかつa３[j]∈Vである

　　

　　　　　また、手順1で表したリテラルのときと同様に、このような場合
　　　　　G={V,E}の頂点カバーであるようなノードの集合V'には、
　　　　　a1[j], a2[j], a3[j]の三つのノードのうち少なくても二つのノードが
　　　　　含まれなければならない

　

　手順3．　G={V,E}においてノードの集合Vは以上で定義されたものですべて表される
　　　　　すなわち、

　　　　　　　

　　　　　　　　　　（※2014年5月7日　V'jの和集合の添え字がmでは無くnになっていました。
　　　　　　　　　　　　                      1≦j≦m　ですので、正しくはmです。お詫びして訂正いたします）

　手順4．　最後にG={V,E}において枝の集合Eについて考えると
　　　　　　すべてのcj∈Ｃについて、cj={xj,yj,zj}と節を表すとき
　　　　　　枝の部分集合を
　　　　　　　
　　　　　　　E"j={　{a1[j], xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
　　　　　と表すことにする

　　　　　こうしたときグラフＧの枝の集合Eを次のように定義する

　

　　　　　

　　　　　　　　（※2014年5月7日　上の図表の式と同じくE'jおよびE''jの和集合の添え字が
                                          mでは無くnになっていました。お詫びして訂正いたします）

また、ここでK=n+2mと定義する

　

　

以上のように翻訳することは明らかに多項式時間以内に可能だということがわかると思います。

　

今回は定義ばかりとなってしまいましたが、このような翻訳作業ということは、Cookの定理やSATを3SATに変換するというところでやったことにも似ています。

　

残りは、このようにして翻訳した結果がVCと同等だということを証明すればいいわけですが、それは次回ということで。

　

それにしてもうっぴょぴょん（乱心）

（※2014年5月7日　手順１.～手順4.までの文字を太線に変更）

頂点カバー問題がNP完全であるということ その１

今回から数回に分けて、頂点カバー問題（以下VCと呼ぶ）がNP完全であることを示していきます。手順としては、３SATがVCへ変換できること、すなわち、数式で書けば　３SAT∝VC　であることを証明することで示します。なお、NP完全についての説明は、「NP完全とその数学的定義　その１、その２」に書いていますので、私のように忘れた方は、もう一度そちらを読み返して下さいね。（え？）
　
念のために要点だけを言っておくと、「NP完全とその数学的定義その２」の終わりに、
　
補題1.3
　L1∈NP, L2∈NP,言語L1はNP完全でさらにL1∝L2ならば言語L2もNP完全である
　
ということを示しています。したがって、SAT∝３SATということから３SATはNP完全であることがすでに証明されていますので、今回も、３SAT∝VC　を証明すれば、VCはNP完全な問題であるということが証明されるわけです。
　
さらに、SAT、３SATがなんであったかさっとさんさっと復習しましょうか。詳しくは、（「充足問題　その１～その３」、「３SAT　その１～その３」の回などを参考にして下さいね）
　
まずSATですが、Uをブール変数（FかTの2値の値しか取らない変数）の集合とし、Cをブール変数の節（例えば{u1,¬u2}や{u1,u2,u4}）の集合(同じく{{u1,￢u2},{u1,u2,u4}}）とします。その時、この節集合CをTとするような、変数の集合Uの各変数の値に矛盾がないか（すなわち、真理関数がTになるか）ということでした。
　
３SATはSATのブール変数の節集合Cの各節のブール変数の数を3に統一するように変形したものでした。覚えてますかね？実は私はよく忘れます（え？）。
　
あっ、えっと、そういう話は置いておいて、さっとさっと説明説明っと。
　
まず、VCがNP困難な問題であることを簡単に述べましょう。あるグラフG(V,E)がありK≦|V|とします。このときK個のノードがVCであるかどうかは、実際に|V|個のノードから選ばれたK個のノードの組を総当たりで調べなければ分かりません。これは多項式時間では調べ尽くせないと言うことは容易に分かります。|V|個のノードから、K個のノードを選んでそれがVCであることを一つ一つ調べていくわけですから、組合わせの数は、オーダー（オーダーについては「クラスPとチューリングマシン その2」を参照して下さい）で|V|のK乗すなわち、最大のオーダーでなら|V|の|V/2|乗になるからです。ちなみに|V/2|の時に最大となるのは、VCとして調べているノードが半分を超えれば、残りのノードの数が少ない方から、VCとして調べているノードへの枝があるかどうかを調べるのと同等だからです。
　
ところが、一旦あるノードの組がVCであるということが分かれば、その場合にVCであることを調べるには多項式時間（クラスP）で済むことは、それらのノードの枝につながっているノードを調べて確認するだけ、ということから容易に分かります。したがって、VCはクラスNPの問題であるということが分かりました。
　
では、３SAT∝VC　であることの証明ですが、それは次回からということで

頂点カバー、独立セット、クリーク その２

今回は、頂点カバー問題（以下VCと略す)、独立セット問題、クリーク問題が本質的に同じ問題だということを示します。ところでここで、本質的に同じってなんでしょうか？この場合は、栄養の面から見れば、料理の見栄えがよかろうが悪かろうが、お腹の中に入ってしまえば同じ、ということとどこか似ています。つまり、数学的にNP完全な問題という面で同じである、として扱えるかどうかということが問題になってくるということです。毎年クリスマスを寂しく過ごした私が言うのもなんですけど、こういうところが女性に人気がないのだと思いますよ、数学。

さて、すでに、前回見たように、頂点カバー問題と独立セット問題は次のような関係にあります。

「あるグラフG=(V,E)が与えられた時、頂点カバーであるようなノードの部分集合V'⊆Vがあるとすると、独立セットであるような頂点の集合はV-V'で表わされる。」

下の図は、前回VCと独立セットを説明する時に使った図ですが、VCの集合に含まれていないノード同士は確かに直接繋がっていないノードの集合になっているのが分かると思います。

では、あるいVCは独立セット問題とクリーク問題はどのような関係にあるのでしょうか。

ここでは、分かりやすく頂点カバー問題とクリーク問題がNP完全と言うことから見て同じであるということを話します。これはやや複雑ですので、図をまず示しましょう。これは先ほど使った図を少しだけ補足説明のために修正したものですが、直感的に見て、VCの補集合である独立セットに属するノードを完全結合できるので、即ち、それでクリークと見なせると言えそうです。

では、もう少しだけ詳しく説明しましょう。まず、先ほども言いましたが、あるグラフG=(V,E)が与えられた時、VCであるような頂点の部分集合V'⊆Vがあるとします。このとき、エッジEcを次のように定義します。

　Ec={{u,v}|u,v∈V, u≠v, {u,v}∉E}

日本語で言えば、グラフGの異なる二つのノードのうちグラフGの枝集合Eに含まれていない枝の集合をEcと定義しますと言うことです。（上の図の赤線の部分）

この時グラフGcをGc={V,Ec}と定義すると、グラフG（とGc）のノード集合VからVCの集合V'∈Vを引いたもの（V-V')はクリークになっているということです。このノードの集合は、独立セットに一致しますよね。

こう考えるとわかりやすいかもしれません。VCでない頂点の集合は独立セットということでした。独立セット同士には直接に結合している枝がありません。集合Ecはその直接繋がっていないノード同士をつなげた枝の集合ですから、その時すなわち、独立セットとして存在していたノードの集合V-V'はその部分では完全結合になっている、ということです。

やっと、ここまで来ました。次回からは数回にわたって、これら三つが３SATに置き換えられることを（問題の複雑さの面という意味では本質的には同等の問題ですので）VCを使って証明します。今度こそさんさっさっと行けばいいのですけど。

2013年12月27日　7:24
　図に間違いがありました。本文の説明も一部間違っておりました。以上の部分を訂正いたしました。こころよりお詫びいたします。

頂点カバー、独立セット、クリーク その１

　さて今回から、グラフ理論における頂点カバー（以下VCと略す）、独立セット、クリークという問題についてしばらく説明します。今回は三つの問題の概念を簡単に説明します。そのあと、これら三つが本質的には同じ問題であるということを説明します。それから、さらに、VC問題がNP完全であることを３SATを使って証明するという流れになります。それは、次回、次々回、次々々回、もしかしたら次々々々回ということになっていくと思います。
　
　では説明に入りましょう。
　
　ちょっとその前に言いたいことがあるんです。よく考えたらですね、３SATを論理式にして、サーキットで表わせば、その問題は、そのままNP完全ですね。実は、この前気づきました。どうもすいません。テヘペロ(死語）
　
　では、どうして、頂点カバー他、このような問題を扱うのか、と言いますと、これらの問題を説明した後、モノトーンなサーキットということを説明していきますが、そのなかで小さなサーキットの部分を近似的にクリーク問題に置き換えて行き、これらの一般的なグラフの問題としてNP完全な問題を扱おう、という方法論がこれまで確立されているのです。それでは、今度こそ説明を始めましょう。
　
　あ、しまった。そうそう、ここで使う用語の説明をやらないといけなかった。
　
これまでこのブログでは集合論的な考え方を基調に説明を行ってきました。そこで、集合論的なサーキットの表現をここで定義しておきたいと思います。具体的には、ノード（頂点(Vertex))の集合をV={v1,v2,…,vn}と表わします。また枝（エッジ(Edge)）では、その集合をEと表わし、各枝は、たとえばノードv1,v2間の枝ならば{v1,v2}と表わします。また、このようなノードと枝をもつグラフGは、
　
　G=（V,E）
　
のように表わすこととします。サーキットとグラフの使い分けが少しややこしいかもしれませんが、我慢して付き合って下さいね。
　
　それでは、今度という今度こそ本題に入ります。
　
　・頂点カバー（Vertex Cover　略してVC）問題
　　　頂点カバー問題とは、あるグラフG=(V,E)が与えられたとしましょう。
　　　その時に任意の枝{u,v}∈Eを取ってきてもそのノードu,vのどちらかが
　　　頂点の部分集合V'⊆Vに含まれるようなV'が存在するかという問題です。

　　　もちろん、V'に含まれる頂点が多いほどそのようなV'は存在しやすくなります。
　　　したがって、最も小さい頂点の集合であるV'を求めるということも
　　　興味深い問題になってきます。こちらは、最小頂点被覆問題とも言い、
　　　NP完全以上の難しさであるNP困難であると言われています。
　　　（参考　http://ja.wikipedia.org/wiki/最小頂点被覆問題)

　

　・独立セット問題
　　　まず独立セットという概念を定義します。
　　　あるグラフG=(V,E)が与えられたとしましょう。
　　　その時に、頂点の部分集合V'⊆Vの任意の頂点の組u,vの間に
　　　エッジのない、すなわち、
　　
　　　　 　　　　　　{u,v}　∉　E
　　
　　　のとき、V'を独立セットと呼びます。
　
　　　独立セット問題とは、グラフG=(V,E)と自然数J≦|V|が与えられたとき、
　　　独立セットV'で|V’|≧Jとなるものが存在するか（あるいはしないか）を
　　　決定する問題ということになります。
　
　　　何となく分かると思いますが、独立セットは頂点カバーの頂点の補集合になります。
　　　したがって、上のVCの例では赤線に囲まれていない部分の頂点が
　　　独立セットであり、この場合少なくても|V’|=4ですので、Jが少なくても
　　　４を満たすということになります。

　　　この場合は、独立セットになる頂点の数が多い方が難しい問題となり、
　　　最も多い頂点の独立セットを求める問題がNP困難な問題となります。


　・クリーク(clique)問題
　　　クリークとはあるグラフG=(V,E)が与えられたとき、頂点の部分集合V'⊆Vが
　　　完全結合になっていることをクリークと言います。
　　　完全結合とは、二つの頂点同士を繋ぐエッジがある、頂点の集団のことです。
　　　エッジがあればその二つの頂点同士は完全に結合していますので、
　　　そういうことを大きさ2のクリークと言います。
　　　つまり、エッジがあればグラフG=(V,E)は、必ず大きさ2のクリークです。

　　　難しい言い方で定義するならば、クリークとは、ある頂点の部分集合
　　　V'⊆Vのどの二つの頂点u,v∈V'を取ってきてもエッジ{u,v}がグラフGの
　　　エッジの集合Eに属している（{u,v}∈E）ということになります。
　
　　　クリーク問題とは、グラフG=(V,E)と自然数J≦|V|が与えられたとき、
　　　クリークである頂点の集合V'で|V’|≧Jとなるものが存在するか
　　　（あるいはしないか）を決定する問題ということになります。
　
　　　また、もっとも大きな頂点の数を持つクリークを求める問題を
　　　最大クリーク問題と言い、最大クリーク問題もNP困難な問題と言われています。
　　　（参考：http://ja.wikipedia.org/wiki/最大クリーク問題）

　　　ちなみにクリークとは派閥とか徒党とかいう意味があるようです。
　　　確かに図を見るとそういう感じがありますよね。

ちなみに私はどちらかというと他人とのつながりがなく、いつもマスメディアにいじめられているという感じです。一般人なのに……。どうでも良いですよね、そういうことは、はい。では次回は上の三つが基本的には同じ問題になることをお話ししたいと思います。

サーキットというグラフ その２

前回まで、簡単にグラフ理論にふれ、サーキットというグラフについて定義しました。今回はもう少しだけ詳しく説明し、そのほかの用語の解説の続きを行います。
　
ところで、ここまでこのブログではいろいろなアメリカのＩＴ企業との関連について（少し無理矢理）触れてきましたが、グラフ理論といえばグーグル。Web上のページをノード、リンクを枝とみなし、インデグリーの数から割り出した順位を、ベージランクと名付けて検索結果における重要度と見なすというのが、基本的なアルゴリズムというのは有名です。私でも知ってますし。そういえば、前回、枝をリンク（link）とも言うと説明しましたね。ちなみにページランクというのは、グーグルの創業者のラリー・ページさんの名前と掛けてあるそうです。ググると分かります。

　

さて、ググってもなかなか出てこない私のブログですが、お話を続けましょう。とほほ。

　

気を取り直して、もう一度サーキットの定義を再掲しましょう。

　

【サーキットの定義】
　いま、ブール変数x1 , … , xnが与えられているとします。グラフは、無サイクルな有方向グラフであり、
　　
　　（１）すべてのノードのインデグリーは0、もしくは、2である
　　　　（１－１）インデグリー0のノードをインプットもしくはリーフと呼ぶ
　　　　　　　　　（一般に、入力であるブール変数x1 , … , xn が相当する）
　　　　（１－２）インデグリー2のノードはゲート（gate）と呼ばれ
　　　　　　　　　∧（論理積）もしくは∨（論理和）が付加されている
　　（２）アウトデグリーの値は任意であるが、アウトデグリー0のノードが
　　　　　ただ一つだけあり、このノードのことをアウトプット(output)と呼ぶ
　
以上を満たすものをこれから、ブール変数x1 , … , xn上のブーリアン・サーキット（Boolean circuit）または、単にサーキットと呼ぶことにする、のでした。
　
ここで、いくつか例を挙げておきましょう。図1は以前「このブログを再開するに当たってのこれからの進め方」でサーキットの例として挙げた図です。インデグリーが２ではないものもありますが、これは、たとえば、図２のようにインデグリー２のグラフに変形できます（ここでは特に節の中（∨で結ばれたもの）だけを変形）。しかし、意味的には元のSAT形式を論理式として考えたときの式と同じでも、直感的な把握は図１の方が勝りますよね。というわけで、実際にはインデグリー２ではなくても意味的にインデグリー２のグラフにできるものも含めて以下サーキットと呼ぶことにします。

　
もう少しだけ、専門用語をお話しして一旦サーキットについての説明を終わりたいと思います。少し予定から先走りしている感じもありますし。
　
まず、論理式Ｆのリーフの数を定義してL(Ｆ)と表すことにします。サーキットＣではL(Ｃ)とも表すことができるのでしょうが、テキストではそこまでは触れていません。また、サーキットの縦の大きさ、これを深さ（depth)と呼びます。またサーキットＣのアウトプットからリーフまでの最大の段数と定義し、d(C)と表します。論理式Fに対しても同じようにd(F)と表わします。ここで、例を挙げるとサーキットで見ると図1と図2では意味的には同じ訳ですが、グラフの形（専門用語ではトポロジーとも言ったりしますが）がちがうわけで、それぞれのグラフの最大の深さをそれぞれ、d(C)=3、d(C)=4と表わすということになるのでちょっと注意が必要です。
　
え？論理式の深さd(F)ですか、さ、3じゃないですか、図１も図２もどちらも同じ論理式ですしね……

じ、実は、この後、論理式やサーキットを、ブール変数 x1 , … , xn から０か１かを与える（ブール）関数fと考えて、fと同じ値を返す論理式Ｆの中で最小のd(F)の値をd(f)とするという定義があるのです……。忘れてました。また、同様にリーフの数L(f)も同様に最小のL(F)の値とするというのがあるのです。随分と面倒ですよね。

グラフ理論についての簡単なお話

私が、電子工学出身と言うこともあり、グラフ理論においての用語は、そちら方面のいわゆる方言を用いているので、元々の数学をご専門とされている方にはなかなかわかりにくいかもしれません。それに、グラフ理論で閉路をサーキットという場合もあるようで、このブログで用いているブーリアン・サーキットと言葉が同じでも全く違った意味で使っているということになっています。

そこでWikipediaの記事をいくつか参考にしながら、標準的なグラフ理論に関しても少しだけ説明させていただきたいと思います（参考文献やそのリンクはその都度示すことにしますが、それ以外にも参考にしたものはこの記事の末尾に示します）

グラフ理論というのは、もともとは、一筆書きから出発したと言われています。その一筆書きにも原点がありまして、１８世紀、プロイセン王国の首都であったケーニヒスベルグに流れる大きな川に架かる７つの橋を同じ橋は二度通らずに一度にすべて渡れるか、という問題に端を発しているようです。これを、オイラーという人が、橋を辺、橋と橋を結ぶ部分を頂点と見なして、一筆書きという形で洗練させて、数学的に解方を示した、ということが元になっているようです（http://ja.m.wikipedia.org/wiki/一筆書き）

このあと、それが位相幾何学として発展していったために、頂点と辺という言葉が数学で一般的に使われるようになったものと思われます（http://ja.m.wikipedia.org/wiki/位相幾何学）

位相幾何学とは、簡単にいうと、すべての図形を点と線だけで分類しよう、という数学の分野です。たとえば、我々が平面に正三角形を書きます。そのとき、一つの角の大きさは６０度です。しかし、地球上にものすごく大きな正三角形を書いたとしたらどうでしょう。地球は球体なので、この正三角形の一つの角度は６０度を超えてしまいます。このように、われわれの正三角形の概念は、実は非常に曖昧です。そこで、点と線の数と結びつき方だけで、図形を分類して性質や特徴について調べようという考え方を発展させていったものが位相幾何学というものなのです。

参考；http://ja.m.wikipedia.org/wiki/グラフ理論