幾何学の問題で質問があります～パート３～

質問

わたしは現在、大学３年生で、昨年度に履修しました幾何学の試験についての質問です。
既に履修してしまい、単位とは関係ないのですが、履修当時、最大流の大問３を含め、完全に回答することができませんでした。
最近数学の復習をしたいと思い、この試験問題を見たのですが、やはり完全な模範解答を作ることができませんでしたので、どの問題でもいいでの、どなたか解説または回答をお願いしてもよろしいでしょうか？

回答No.2

stomachman · ベストアンサー

変な回答に反応しない所を見ると「最大フロー」が何のことなのかは一応分かっていらっしゃるのかも知れない．しかし，「幾何学の問題」と分類するのはあんまり普通じゃないなあ．
　おそらくこれは，問題を解くためにいかに数学を応用するかという（この場に最もふさわしい）話じゃなくて，単に「最大フロー最小カット定理」を理解しているか，あるいは最大フロー問題はソモソモ「線形計画法」に他ならないということを理解しているか，という基礎知識の話ではないかな．
　もし，知識は十分あるのにそれでも自力で答が出せないのなら，何をどうやってどこで行き詰まったかを詳細に補足なさるとよろしいかと．

回答No.1

muturajcp

AからLまでの経路の数字の合計が最大となる経路は
A→C→F→H→J→L
(AC=2)+(CF=9)+(FH=1)+(HJ=5)+(JL=5)=(ACFHJL=22)

max(AE)=max(ABE=7,AE=9,ACE=8)=(AE=9)
max(AG)=max(ABDG=8,AEG=10)=(AEG=10)
max(AH)=max(AEH=11,ACFH=12)=(ACFH=12)
max(AJ)=max(AEGJ=15,ACFHJ=17)=(ACFHJ=17)
max(AK)=max(ACFHK=18,ACFIK=15)=(ACFHK=18)
max(AL)=max(ACFHJL=22,ACFHL=21,ACFIKL=21)=(ACFHJL=22)