← 図１ これは単純な一本道。
← 図２ ぶつかっても、そこでやめればＯＫ。
← 図３ でも、さらに続けるのはダメ。
最長片道きっぷの経路を求める問題を解くにあたって、 解きかたを決める手がかりになるよう、問題を少し分析します。
突然ですが、以下では、
最長片道きっぷの経路を求める問題を
LOP（Longest Oneway-ticket Problem）と呼ぶことにします。
造語ですが、万が一これが定着したらうれしいなぁ。
そして、発売条件を満たす経路を LOP の許容解、
許容解の中で最長のものを最適解と呼ぶことにします。
つまり、現在の目標は「LOP の最適解を求めること」です。
まず最初に、導入部でちょっと触れた「片道乗車券の発売条件」 をもう少し詳しく考察してみます。そして、 どのような形状の経路なら片道乗車券が発売されるのかを明らかにします。 ちょっとエラソーに言えば「トポロジー的分類」です。
「片道乗車券」と聞くと「一本道」というイメージが浮かぶかもしれません。 しかし、必ずしもそうではありません。発売条件をよく読むと、 もっと別の形の片道乗車券も発売されることが分かってきます。
前述のとおり、 ある経路に対して片道乗車券が発売されるための条件（発売条件）は、 その経路に対して
が同時に成り立つときのみでした。そして、この条件を満たす限りは、
任意の経路に対して片道乗車券が発売されます。
この発売条件を満たすものとして、
まず真っ先に考えられるのは、同じ駅を２度通らない「一本道」の経路です。
このような経路が発売条件を満たすことは明らかです。
が、同じ駅を２度通ったら必ずダメ、というわけでもありません。
発売条件で禁止されているのは「環状線一周を超えるとき」なので、
ちょうど「環状線一周」なら片道乗車券になるのです。
つまり、同じ駅を２度通っても、
２度目にその駅に到達したところで経路を打ち切れば、
それは発売条件を満たすのです。
ですから、たとえば山手線一周（円形）は片道乗車券になりますし、
横浜から品川に至り、山手線を一周してまた品川に至る「６の字」
形の経路も片道乗車券になります（図１〜３）。
← 図１ これは単純な一本道。
← 図２ ぶつかっても、そこでやめればＯＫ。
← 図３ でも、さらに続けるのはダメ。
そのいっぽう、一般的な「一筆書き」では許容されている「８の字」「日の字」 は発売条件を満たしません。たとえば「８の字」に関して言えば、 「８」の中心で４本の線が交わっているので、 この場所を少なくとも２回訪問しますが、発売条件は「２回目の訪問のあと、 さらに先に進むこと」を許していません（図４）。
← 図４ 「一筆書き」とは微妙にちがうんです。注意。
以上から、発売条件を満たす経路、すなわち片道乗車券の発売される経路は、 トポロジー的に分類すると以下の３通りになります。 ３種類をそれぞれアルファベットに見立て、名前をつけてみました。 これらの命名は宮代くんによるものです。
Ｌ、Ｏ、Ｐときれいにそろいました。これが「LOP」の由来の１つです（図５）。
← 図５ きれいにオチがつきました。
このうちタイプＰについては注意が必要です。
タイプＰの経路は逆向きにできないのです。
たとえばさきほどの例ですが、「横浜→品川→山手線一周→品川」
というタイプＰの経路は発売条件を満たしていました。
品川駅を２度通るものの、２度目に通ったところで経路が終わっているからです。
しかし、これを逆向きにして「品川→山手線一周→品川→横浜」とすると、
発売条件を満たさなくなります。
品川を２度通るのに、２度目の品川で経路を打ち切っていないからです（図６、７）。
← 図６ こっち向きならＯＫですが…
← 図７ 逆向きは×。品川で打ち切らねばなりません。
片道乗車券が発売できる以上、その経路はタイプＬ、タイプＯ、
タイプＰのいずれかである、ということが分かりました。
したがって、最適解はこの３つのうちのどれかということになります。
が、実際にはもっと最適解の候補を狭めることができます。
この節では、最適解がどのタイプで、発着駅がどういった駅か、
ということを明らかにします。
まず、ＪＲの具体的な路線図を見ると、
明らかにタイプＯの経路は最適解になれないということが分かります。
ＪＲの路線図全体はタイプＯではありませんし、ＪＲの路線図は「連結」で、
ある部分が他の部分から孤立しているということもありません。
したがって、もしタイプＯの経路が１つあれば、
それに１本「ひげ」を加えたタイプＰの経路が最低１つは必ず作れます。
当然、そのタイプＰの経路のほうが距離は長くなるので、
タイプＯには出番がないことになります。
また、残ったタイプＬやタイプＰにしても、どこを発駅にしてどこを着駅にするか、 ということに関してはそれほど選択の余地がありません。 具体的には、最適解の発着駅としては、 行き止まりの駅、分岐駅、分岐駅に隣接する駅のいずれかだけを考慮すればよいのです。
まずタイプＬに関して、
最適解の発着駅がどのような場所になるかを考えてみましょう。
最適解というからには、
いかなる方法をもってしてもそれより長い経路を作れません。
したがって、最適解の発着駅は、
「そこから一歩でも進むともうダメ」という「限界の駅」になっているはずです。
そのような駅として考えられるのは、
そこから一方向にしか線路の出ていない駅、つまり行き止まりの駅です。
以後、これを終端駅と呼ぶことにします。
次にタイプＰに関してです。
着駅は明らかに、３方向以上に線路の出ている駅（以後、
これを分岐駅と呼びます）しかあり得ませんが、
発駅に関しては選びようがあります。
タイプＬと同じく、終端駅は最適解の発駅となり得ますが、
その他の駅にも可能性はあります。
その駅から先に、まだ通ったことのない線路が残っているけれど、
１駅延長すると発売条件を満たさなくなる（タイプＰでなくなる）、という場合です。
具体的には、分岐駅に隣接する駅が最適解の発駅となることが考えられます。
１駅延長すると、あとで通る分岐駅に行き当たってしまい、
タイプＰでなくなるというわけです（図８、９）。
← 図８ これはＮＧですが…
← 図９ １駅だけ短くすればＯＫ。
だから「ぶつかる１駅手前から出発する」という最適解もあり得るのです。
このように「１駅延長するとタイプが変わる」ということはタイプＬでもあり得るのですが、 タイプＬの場合、タイプが変わったとしてもタイプＰになるだけですから、 １駅延長しても依然として発売条件を満たしています。 したがってタイプＬでは分岐駅の隣接駅発を考慮する必要がありません。
以上の考察をまとめると、 最適解は以下の３つのうちのどれかであることが分かります。
ここで「タイプ Lee」などの新たな表記法を導入しましたが、
「e」は終端駅、「n」は分岐駅に隣接する駅を表すと考えてください。
たとえばタイプＬのうち、発駅が「e」、着駅が「e」のものがタイプ Lee です。
前述のとおり、タイプ Len なんてのは考えなくてかまいません。