
武蔵野個別指導塾の特徴
共通テスト情報I 通信経路と線の切断—別の道が残るか接続表からたどり直す|武蔵野個別指導塾

接続表から故障した線を除き、迂回できる場合と届かない場合を比べて通信経路をたどりましょう。
よくあるのは、高校生がネットワークの線が1本切れたと聞き、全端末が通信不能になると考える場面です。切れた線を使う道は通れませんが、別の線をつないで宛先まで進めることもあります。一方、別の道がありそうに見えても、その道の途中に切れた線が含まれていれば使えません。線を1本除いた後の接続関係を見直し、送信元から到達できる端末を順に集めて判断します。
何を固定し、何を変えるか
問われ方には、切断後も指定された宛先へ到達できるかを判定する型と、切断前後に到達できる端末の集合を比べる型があります。さらに、切る線を候補ごとに変え、到達不能になるものを選ぶ型もあります。いずれも、端末と線の一覧、送信元、故障する線を読み取るところから始めます。
ここでは一覧の線を無向とします。例えば A-B は A から B、B から A のどちらにも進める1本の線です。切断はその1本を両方向とも使えなくする操作です。端末自体や他の線は正常で、残った線を任意の順に使えるものとします。代替経路を利用できる条件は、切断後の残った線だけで送信元から宛先まで連続してたどれることです。この条件は問題のための単純な約束であり、現実に機器が自動で経路を切り替える保証ではありません。
到達可能という答えには、実際に残った線を並べた経路を添えます。到達不能という答えには、送信元から広げた集合と、その外へ出る残りの線がないことを添えます。経路が1つ見つからなかっただけでは、別の経路がないことまでは示せないからです。
接続表を使う順序
端末を点、直接つながる線を辺と呼びます。経路は隣り合う端末の間に辺がある並びです。接続表では、各行の端末から1本で行ける相手を書きます。無向の A-B なら A の行に B、B の行に A を書きます。線の一覧にない組を、図の近さや名前の順番だけでつなげてはいけません。
図1のように、A-B、B-C、A-C、C-D の4本を考えます。A、B、C は輪になり、D へは C-D でつながります。輪の1本 A-B を除いても A-C-B という道があります。しかし C-D を除くと D に入る残りの線はありません。切断前にすべてつながっていることと、どの1本を除いてもつながることは別の条件です。

図1では、線の位置より端点の組が判断の根拠です。線が交差して見えても交点が端末と指定されなければ、そこで乗り換えられるとは限りません。逆に図がなくても、辺一覧から接続表を作れば同じ判定ができます。
送信元から到達先を集めるには、まず送信元を集合に入れ、その集合に入った端末に隣接する端末を追加します。新しい端末がなくなるまで繰り返せば、集合内から残りの線で外へ出る道はありません。送信元も、自分自身に到達できる端末として数えます。訪問済みの端末へ戻っても再び追加しないので、輪の中をいつまでも回らずに済みます。
基本例題:輪を回って目的地へ
端末 P、Q、R、S の無向の辺一覧は P-Q、Q-R、R-S、P-S、Q-S です。線 P-Q が故障し、他の線と端末は正常です。切断後の残りの線を連続して使える場合に代替経路を利用できるとします。P から R に到達できるかを答え、できる場合は経路を1本、できない場合は P から到達できる端末の集合を示してください。また、切断前後の P からの到達先をそれぞれ集合で答えてください。
図2のように P-Q を除きます。切断前の P の隣は Q と S ですが、切断後は S だけです。S から R と Q へ進めるので、P からの集合は P、S、R、Q と広がります。R が入ったため到達可能で、経路の一例は P-S-R です。P-S と S-R はどちらも辺一覧にあり、故障した P-Q を含みません。

切断前の到達先は {P, Q, R, S}、切断後も {P, Q, R, S} です。図2の経路を逆からたどると R-S-P も残る線だけで構成され、無向の条件に合います。すべての端末に届くという結論は、この辺一覧とこの故障に限ったものです。Q-S がなくても P-S-R-Q という経路は残りますが、別の線を切ったときの結論は改めて調べる必要があります。
標準例題:端にある端末の切り離し
端末 A、B、C、D、E の無向の辺一覧を A-B、B-C、C-A、C-D、D-E とします。C-D が故障し、それ以外の線と端末は正常です。残った線の連続した経路を使えるときに代替経路を利用できるとします。A から E へ到達できるか、切断前後の A からの到達先の集合とともに答えてください。
切断前は A から B、C へ、C から D、さらに E へたどれます。到達先は {A, B, C, D, E} です。切断後は A の隣が B と C、B の隣が A と C、C の隣が A と B です。集合 {A, B, C} から外へ出る残った線はありません。したがって到達先は {A, B, C}、E には到達不能です。
D-E の線は残っていますが、A 側から D へ渡る線がありません。E の側に正常な線があることは、A からその線にたどり着けることを意味しません。逆に D を送信元とすれば、切断後の到達先は {D, E} です。送信元を変えたときは集合の出発点も変えて考えます。
発展例題:故障する線を比べる
端末 J、K、L、M、N の無向の辺一覧は J-K、K-L、L-J、L-M、M-N、N-L です。端末と、指定した1本以外の線は正常です。残った線で連続してたどれる場合に代替経路を利用できるとします。故障する線が J-K の場合と L-M の場合について、J から N へ到達できるか、それぞれ経路を1本ずつ示してください。2本を同時に切る条件ではありません。
J-K を除く場合は J-L-N と進めます。J-L と L-N は一覧に残っています。L-M を除く場合も J-L-N が使えます。後者では J から M へも J-L-N-M と進めるため、切った線の両端も別の道でつながっています。どちらの故障でも J からの到達先は {J, K, L, M, N} です。
ここで各場合を元の一覧から始めることが大切です。J-K を除いた表からさらに L-M を除くと、指定と違う2本の故障を調べてしまいます。また、今回の到達可能は残った辺に経路があるという判定です。経路の選択や切替の動作、実際にデータが届くまでの時間は、この条件からは決まりません。
誤答を接続表へ戻す
図3の無向の辺一覧は U-V、V-W、W-X、V-X、X-Y です。V-W が故障し、他の線と端末は正常です。残った線を連続して使える場合に代替経路を利用できるとします。U から W へは到達できない、と答えたとします。理由を「U-V-W の途中が切れたから」とする答えです。

図3の誤りは、最初に試した経路が使えないことから、他の経路も使えないと決めた点です。故障した V-W を除くと、U の隣は V、V の残った隣は U と X です。X から W へ進めるので U-V-X-W が残ります。隣接する組を1本ずつ一覧に戻して照合すると、故障線を使わずに到達できます。Y へも U-V-X-Y で到達できます。
反対の誤りもあります。図3で X-Y が故障した場合に、U-V-X まで到達できたことだけを見て Y にも届くとする答えです。Y につながる辺は X-Y しかないため、これを除くと Y に入れません。Y の接続先を確認すれば、届かない理由を示せます。残った線を見落とす誤りと、存在しない線を補う誤りの両方を、接続表の各行で修正します。
接続表の更新を確かめる
故障前の表を写したら、故障線の両端に注目します。例えば A-B を除くなら A の行の B と B の行の A をともに消します。他の行まで消してしまうと、正常な線を失った別の問題になります。元の表と更新後の表を比べ、変わった2か所が指定された1本に対応するか調べます。
到達先を広げるときは、その時点で集合に入った端末から直接つながる相手だけを追加します。まだ集合にない端末から先を調べる前に、その端末に至る線を確保します。候補が複数あるときの調査順は自由ですが、最後の集合は同じです。途中で宛先が見つかった場合も、集合全体を問われているなら、残る端末について確認を続けます。
線が切れると、到達先が減ることはあっても増えることはありません。残った線だけの経路は切断前にも存在していたからです。切断後の集合に切断前にはなかった端末が現れたら、表の読み違いや故障前の探索漏れが疑われます。ただし集合が変わらないことだけでは、切断前と同じ経路を使えるとは限りません。基本例題では P-Q が使えなくなり、残る道をたどり直しました。
到達不能を説明する際、宛先の隣に線が残っていても、その隣まで送信元から行けるとは限りません。標準例題の D-E がその例です。送信元側の集合から外へ出る線を全部調べる方法なら、宛先側に残る部分だけを見て判断する誤りを避けられます。集合の境界を確かめる作業は、別の経路の見落としがないことを説明するためにも役立ちます。
自分で確かめる5問
各問で辺は無向です。指定された1本以外の線と端末は正常で、残った線を連続してたどれる場合に代替経路を利用できるものとします。到達先の集合には送信元自身を含めます。到達可能なら経路を1本、不能なら送信元からの到達先の集合も示してください。
- 端末 H、I、J、K の辺は H-I、I-J、J-K、K-H です。H-I が故障したとき、H から J へ到達できますか。切断前後の H の到達先も集合で答えてください。
- 端末 T、U、V、W、X の辺は T-U、U-V、V-T、V-W、W-X です。W-X が故障したとき、T から X へ到達できますか。切断前後の T の到達先を集合で答えてください。
- 端末 A、D、F、G、H の辺は A-D、D-F、F-G、G-D、G-H です。D-F が故障したとき、A から H へ到達できますか。経路と切断後の到達先を答えてください。
- 端末 B、C、E、F、G、H の辺は B-C、C-E、E-B、E-F、F-G、G-H です。E-F が故障したとき、B から H へ到達できますか。切断前後の B の到達先を集合で答えてください。
- 端末 M、P、Q、R、T の辺は M-P、P-Q、Q-M、Q-R、R-T、T-Q です。故障する線が M-P の場合と Q-T の場合を別々に調べ、M から T への到達可否と経路、切断後の到達先をそれぞれ答えてください。
解答とたどり方
-
到達できます。H-I を除くと H から K、K から J へ進めるので H-K-J が経路です。J から I にも進めます。切断前後とも到達先は {H, I, J, K} です。経路の H-K と K-J がともに一覧に残ることも確認します。
-
到達できません。切断前は T から V、W を経て X へ進め、到達先は {T, U, V, W, X} です。切断後は T、U、V の輪から W までは行けますが、X につながる W-X がありません。到達先は {T, U, V, W} で、この集合から X へ出る残りの線はありません。
-
到達できます。A-D-G-H が経路です。D-F は使いません。A から D、G、H に進み、G から F にも進めるので、切断後の到達先は {A, D, F, G, H} です。経路の D-G は一覧の G-D と同じ無向の線です。
-
到達できません。切断前は B-C-E-F-G-H などをたどり、到達先は {B, C, E, F, G, H} です。切断後は B、C、E の間で広がりますが、集合 {B, C, E} から外へ出る線が残りません。F-G と G-H は正常でも B 側からそこへ入れません。
-
M-P が故障した場合は M-Q-T、Q-T が故障した場合は M-Q-R-T で到達できます。前者は Q から P と R にも進め、後者は Q から P、R、さらに T に進めます。どちらも到達先は {M, P, Q, R, T} です。各経路にはその場合の故障線が入っていないことを、元の辺一覧へ戻して確かめます。
覚えておくこと
- 無向の切断は、その線を両方向から除きます。
- 到達可能は残った線だけの経路を示します。
- 到達不能は到達集合から外へ出る線がないことを示します。
- 故障候補を比べるときは毎回元の辺一覧から始めます。
- 経路の存在と自動切替の動作は別に考えます。
どこで迷ったかを見分ける
答えが合わないときは、まず故障線の両端の行を見ます。片方の行だけから相手を消していれば、無向の条件の読み落としです。次に到達集合を広げる順を見ます。新たに入った端末の隣を調べていなければ、迂回路を途中で止めています。
個別指導で説明を確かめるなら、経路の隣り合う端末を一組ずつ辺一覧に指し戻してもらいます。到達不能の場合は、集合の中の全端末について、残る隣接先が集合内に収まるかを確認します。図の見た目だけに頼らず、残った接続を根拠に到達先を判定できます。
もう「日東駒専」を目標にしないでください。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。




