高校数学C 離散グラフの表現—地図から位置を省き接続関係を頂点と辺に直す｜武蔵野個別指導塾

交差を乗換地点にする条件を読み分け、図を描き直しても直接つながる頂点の組が保たれるかを辺の一覧で照合します。

よくあるのは、理系の高3が路線の略図を見て、線が交差する場所をすべて乗換地点にしてしまう場面です。紙の上では線が重なって見えても、立体交差で行き来できない場合があります。逆に、曲がった線や長い線も、途中に停留所がなければ両端を結ぶ1本の辺として表せます。何を地点とし、どこで移れると定めたかが、図を読む出発点です。

接続を問う問題の出方

まず、地点と区間の説明からグラフを描き、辺の一覧を作る問題があります。距離や方角を省いても、直接つながる地点の組が変わらなければ、接続を表すグラフとして同じです。ただし、途中の停留所を省くと直接の接続が変わります。省いてよいのは位置や線の曲がり方であり、指定された地点ではありません。

次に、2枚の図が同じ接続を表すかを判断する問題があります。頂点に同じ名前が付いているなら、各名前の組について辺の有無を照合します。左右の位置や辺の長さを比べる必要はありません。名前のない図では、対応する頂点を決め直してから照合します。頂点数や次数が一致することは候補を絞る手掛かりですが、それだけでは辺の対応が保証されません。

さらに、交差を地点にする条件を変更して、頂点数や辺数がどう変わるかを問うこともあります。交差の前後で元の区間をどう分割したかを記録すれば、見た目に頼らずに数え直せます。ここでのグラフは、地点間の直接の接続を表す道具です。所要時間や実際の距離の大小は、この情報だけからは判断しません。

点と線に残す情報

離散グラフでは、対象となる地点を頂点、直接結ぶ区間を辺で表します。ここでは辺に向きがなく、同じ2頂点の間に複数の辺を置かず、同じ頂点から自分自身へ戻る辺も置かない無向単純グラフを考えます。辺 AB は辺 BA と同じ1本です。頂点に接続する辺の本数をその頂点の次数といいます。

図1のように、A と C を結ぶ線と B と D を結ぶ線が紙の上で交差していても、その交差に頂点を置くかは別の条件です。左は交差点で移れず、右は交差点 X で移れる場合です。左では辺は AC と BD の2本、右では AX、CX、BX、DX の4本です。右の X は次数4ですが、左の交差には次数を付ける頂点そのものがありません。

図1の2つは線の形が似ていても接続が違います。左で A から B へ移るには、与えられた辺だけでは方法がありません。右では A から X を経て B に移れます。辺が交差するという視覚上の事実から乗換可能と決めず、問題文の指定を先に読みます。

辺の一覧を書くときは、例えば AB、AC のように両端の名前を並べます。辺の途中に頂点 X がある場合、AX と XB に分け、AB を直接結ぶ辺として数えません。別に AB という直接区間が与えられていれば話は変わりますが、その場合も図の線ごとに両端を確認します。1つの頂点から他の頂点へ何が接続するかを表にすれば、描き直した図の点検にも使えます。

辺を1本数えると、その両端の次数に1ずつ加わります。したがって次数の合計は辺数の2倍です。これは数え漏れを探すための検算です。ただし合計が一致しても、誤った辺を別の誤った辺に取り替えれば合計は変わりません。各辺の両端を元の条件と照合して初めて、場面の接続まで確かめられます。

基本例題：通路の交差を読み分ける

架空の施設に入口 A、展示室 B、休憩室 C、出口 D があります。直接通れる通路は AB、BC、CD、DA、AC の5本です。AC と BD を結ぶ線が図の上で交差するように描けますが、BD は通路ではありません。AC と他の通路は端点以外で交差しても行き来できません。無向単純グラフとして辺を列挙し、各頂点の次数と辺数を整数で求めてください。

図2のように4地点を四角形の頂点として置き、条件にある5組を線で結びます。線の配置は理解の助けですが、辺の有無は通路の一覧で決めます。対角線 BD は指定されていないので追加しません。

A に接続する辺は AB、AD、AC です。したがって A の次数は 3 です。同様に各頂点から辺を拾うと、次のようになります。

A: AB、AD、AC → 3
B: AB、BC → 2
C: BC、CD、AC → 3
D: CD、AD → 2
次数の合計 = 3 + 2 + 3 + 2 = 10
辺数 = 10/2 = 5

図2で A と C の間を直接結んでいますが、その線の長さは通路の長さを表していません。辺数を元の条件に戻すと、外周の4本と AC の1本で5本です。B と D の線を想像して交差を作っても、それは与えられた通路になりません。確認の順序は、辺を作る、各端点から次数を数える、元の5組と照合する、の順です。

もし AC と BD がともに実際の通路で、交差で移れないという別の条件なら、BD を6本目として加えます。このとき交差点には頂点を加えません。一方、交差で移れるなら、交差を新しい頂点として両方の通路を分割します。どちらの変更も元の問題の答えではなく、条件を変えた場合の比較です。

標準例題：描き方が違う2枚を比べる

架空の連絡網に頂点 P、Q、R、S、T があり、直接の連絡は PQ、QR、RS、ST、TP、PR です。別の図では、直接の連絡が PQ、QR、RS、ST、TP、QS と書かれています。名前は同じ対象を表します。2つの図が同じ接続を表すか答え、異なる場合は違いを辺で示してください。辺は無向で、交差は頂点ではありません。

まず、それぞれの辺を同じ順に比べます。最初の5組は一致し、最後の組が異なります。

共通の辺: PQ、QR、RS、ST、TP
前者にあり後者にない辺: PR
後者にあり前者にない辺: QS

よって、同じ名前の頂点を対応させると同じ接続ではありません。前者では P と R が直接連絡できますが、後者ではその組は直接つながっていません。逆に Q と S は後者で直接つながります。図を回転したり辺を曲げたりしても、この違いは解消しません。

次数も計算して点検します。前者の P、Q、R、S、T の次数は順に 3、2、3、2、2 です。後者は順に 2、3、2、3、2 です。どちらも合計は 12 で、辺数は6本です。次数の合計と辺数が一致していても、同じ名前の頂点の接続は異なります。元の連絡先の一覧を照合する必要があることが、この例から見えます。

なお、頂点の名前を付け替えてよい問題なら、ここでの判定条件とは異なります。例えば前者の P、Q、R、S、T を後者の Q、R、S、T、P にそれぞれ対応させると、6本の辺が後者の6本に対応します。名前を固定するかどうかを、図形の見た目より先に決めます。

発展例題：交差を地点にすると何が増えるか

架空の広場に地点 U、V、W、Z があり、通路 UV と WZ がそれぞれ途中に地点を持たずに交差しています。ほかに通路 UW が1本あり、他の交差はありません。はじめは交差点で通路を乗り換えられません。その後、交差点に出入口 X を設け、そこで両方の通路を行き来できるようにします。変更前後の頂点数、辺数、各頂点の次数を整数で求めてください。

変更前は、交差点を頂点として扱いません。3本の通路の両端をそのまま辺として書きます。

頂点: U、V、W、Z
辺: UV、WZ、UW
頂点数 = 4
辺数 = 3
次数: U は2、V は1、W は2、Z は1
次数の合計 = 2 + 1 + 2 + 1 = 6 = 2・3

変更後は UV を UX と XV に、WZ を WX と XZ に分けます。UW は途中に新しい地点がないのでそのままです。元の UV と WZ を、新しい4本に加えて再び数えることはしません。

頂点: U、V、W、Z、X
辺: UX、XV、WX、XZ、UW
頂点数 = 5
辺数 = 5
次数: U は2、V は1、W は2、Z は1、X は4
次数の合計 = 2 + 1 + 2 + 1 + 4 = 10 = 2・5

新頂点は1個、辺は2本増えました。2本の辺を取り除き、4本を加えた結果です。元の場面に戻すと、変更後は V から X を経て Z に移れます。変更前は UV、UW、WZ を順に通れば V から Z に移れますが、交差点で直接乗り換えることはできません。到達できるかどうかが同じでも、直接の接続や通る区間の並びは変化します。

この変化量は、2本の辺がそれぞれ内部の1点で交差し、その1点だけを新しい頂点にするという条件によります。3本が同じ点で交差する場合や、もともと端点だった場合に、そのまま2本増えると決めてはいけません。条件を読んで、分割前に何本あり、分割後に何本になるかを数えます。

誤答から交差の意味を直す

図3の左のように、辺 AC と BD が交差する図に対し、何も指定されていないのに交点 X を頂点として書く誤答を考えます。すると本来は2本だった辺を4本と数え、A から B へ X を通って移れると判断してしまいます。原因は、紙の線が重なることと、実際に乗換が可能であることを同一視した点です。

図3の右では、交差を頂点にしない条件に従って、辺 AC と BD をそれぞれ端から端までたどります。交差の位置に名前を付けず、2本の辺の一覧を残します。交差で乗り換えられるという明示がある場合は、逆に X を付け、4本に分けるのが正しい修正です。図の上に点が描かれていても、凡例や問題文でその点の意味を確かめます。

もう1つの誤りは、線を曲げて描き直す際に途中で別の頂点を通してしまうことです。直接の辺 AC を A、B、C と通る2本に変えると、B が新たな接続先となります。描き直す前後で、各頂点の隣にある頂点の一覧を比較しましょう。次数の合計が一致したという確認に加えて、相手の名前まで照合すれば、この種の取り違えを見つけられます。

練習問題

いずれも無向単純グラフとし、明示されない交差は頂点ではありません。答えは辺の一覧または整数で示してください。

1. 架空の倉庫の区画 E、F、G、H の直接通路は EF、FG、GH、HE、FH です。各区画の次数と辺数を求めてください。
2. 地点 J、K、L、M で、辺 JK と LM が途中で交差します。交差で乗り換えられません。辺の一覧と頂点数を求め、J から M に移れるか答えてください。他の辺はありません。
3. 問2とは別の図で、地点 A、B、C、D を結ぶ辺 AB と CD が内部の1点 Y で交差し、Y で乗り換えられます。辺の一覧と Y の次数を求めてください。他の辺はありません。
4. 同じ名前の頂点 N、O、P、Q を持つ2図の辺が、それぞれ NO、OP、PQ、QN と NO、OP、PQ、NP です。接続が同じか判定し、異なる辺を挙げてください。
5. 架空の配線図の頂点 R、S、T、U、V の辺は RS、ST、TR、TU、UV です。各頂点の次数と辺数を求め、次数の合計からも確かめてください。

練習問題の解答と解き方

1. E には EF、EH の2本、F には EF、FG、FH の3本、G には FG、GH の2本、H には GH、HE、FH の3本が接続します。次数は順に 2、3、2、3、辺数は5本です。合計は 2 + 3 + 2 + 3 = 10 で、辺数の2倍に一致します。元の通路5組を1本ずつ確認すると、いずれも両端で1回ずつ数えられています。

2. 辺は JK、LM の2本、頂点数は4です。交差に頂点を作らないので、J の隣は K、M の隣は L です。ほかの辺がないため、J から M へは移れません。線を交点で4本に切ると、問題文の乗換不可という条件を失います。

3. 辺は AY、YB、CY、YD の4本で、Y の次数は4です。AB と CD はそれぞれ Y によって分割されます。A から B に至る元の区間が AY と YB に対応し、C から D に至る区間が CY と YD に対応することを確認します。Y で A 側から D 側へ移れる点も指定どおりです。

4. 同じ接続ではありません。前者に QN があり、後者にはなく、後者に NP があり、前者にはありません。残る NO、OP、PQ は共通です。前者の Q の隣は P と N、後者の Q の隣は P ですから、元の頂点名のままでも違いを確かめられます。

5. R、S、T、U、V の次数は順に 2、2、3、2、1 です。辺数は5本です。次数の合計は 2 + 2 + 3 + 2 + 1 = 10 であり、10/2 = 5 となります。元の配線に戻し、三角形の RS、ST、TR と、そこから延びる TU、UV の計5本を照合します。

覚えておくこと

地点を頂点、直接の接続を辺として残します。 交差を頂点にするかは条件で決まります。 辺の両端の一覧を比べ、位置や線の形に惑わされないようにします。 次数の合計は辺数の2倍ですが、それだけで接続の一致は保証されません。

つまずきの見分け方

答案で交差に印が追加されていたら、まず元の図と文章のどちらを根拠にしたかを尋ねます。交差の扱いを口頭で説明できても、辺の一覧に分割前の辺と分割後の辺を同時に残していることがあります。その場合は各通路を指で端から端までたどり、途中の頂点ごとに区間を区切った記録を確認します。

個別指導では、描いた図だけでなく、頂点ごとの接続先の一覧と次数の計算も見ます。次数が合っていて一覧が違えば相手の取り違え、一覧は合っていて次数が違えば数え漏れが疑われます。図と一覧の両方を元の条件に戻す習慣が、接続関係を正確に表す土台です。