Кіріспе
Граф теориясындағы есептеу мәселесі
Оптимизация теориясында максималды ағын мәселелері – ағын желісі арқылы максималды мүмкін болатын ағын мөлшерін қамтамасыз ететін қолданылатын ағынды табуды қамтиды. Максималды ағын мәселесі циркуляция мәселесі сияқты күрделі желілік ағын мәселелерінің ерекше жағдайы ретінде қарастырылуы мүмкін. S-тен t-ге ағынның ең жоғары мәні (яғни, бастапқы нүкте s-тен түпкі нүкте t-ге ағын) желідегі s-ті t-ден бөлетін кесудің (яғни, s-t кесу) ең төменгі сыйымдылығына тең, бұл max flow min cut теоремасында айтылған.
Тарих
Максималды ағындылық проблемасын алғаш рет 1954 жылы Т. Э. Харрис пен Ф. С. Росс совет темір жолының трафигін модельдеудің оңайлатылған түрі ретінде қойды. 1955 жылы Лестер Р. Форд, кіші, және Делберт Р. Фулкерсон алғашқы белгілі алгоритмді, Форд-Фулкерсон алгоритмін жасады. 1955 жылғы мақалаларында Кельнер, Ли, Орексия және Сидфорд шамамен оңтайлы максималды ағынды табады, бірақ бұл тек бағытталмаған графтар үшін ғана қолданылады. 2013 жылы Джеймс Б. Орлин алгоритмді сипаттайтын мақала жариялады. Бір бастап нүктеден ең қысқа жол (SSSP) мәселесі үшін, теріс салмақтары бар және ең төменгі құн ағыны мәселесінің тағы бір ерекше жағдайы үшін, дерлік сызықтық уақытта жұмыс істейтін алгоритм де хабарланды. Екі алгоритм де 2022 жылғы Компьютер ғылымының негіздері жөніндегі симпозиумда ең жақсы мақалалар деп танылды.
Көп көзді көп сорғышты ең жоғары ағындылық проблемасы
Бір ғана көз және бір тұнбаның орнына, көздер жиыны мен тұнбалар жиыны бар желі берілген. Біз осы желі арқылы ең үлкен ағынды табуымыз керек. Көп көзді, көп тұнбалы мәселені ең үлкен ағыс мәселесіне айналдыру үшін, әрбір көз нүктесіне қосылатын бірыңғай көзді және әрбір тұнба нүктесіне қосылатын бірыңғай тұнбаны (сонымен қатар суперкөз және супертұнба деп те аталады) қосамыз. Осы әрбір қабырғаның сыйымдылығы шексіз болады (4.1.1-суретті қараңыз).
Екі жақты сәйкестіктің ең жоғары кардиналдылығы
Екі жақты граф берілгенде, біз оның ең үлкен түбірлік сәйкестігін табуымыз керек, яғни, ең көп санды жиектерді қамтитын сәйкестікті. Бұл мәселені максималды ағын мәселесіне түрлендіруге болады, үшін желі құру арқылы, онда графтың барлық жиектерінен бастапқа бағытталған және әрқайсысы үшін және әрқайсысы үшін (4.3.1-суретті қараңыз). Содан кейін желідегі максималды ағынның мәні графтың ең үлкен сәйкестігінің өлшеміне тең болады, ал ең үлкен түбірлік сәйкестікті интегралды максималды ағындағы ағыны 1-ге тең жиектерді таңдау арқылы табуға болады.
contains the edges in directed from to for each and for each for each (See Fig. 4.3.1). Then the value of the maximum flow in is equal to the size of the maximum matching in , and a maximum cardinality matching can be found by taking those edges that have flow in an integral max flow.
Бағытталған ациклді графиктегі жолдың ең төменгі қалыңдығы
Бағытталған ациклді граф берілгенде, біз графтың әр төбесін қамту үшін төбелері өзара қиылыспайтын ең аз жолдар санын табуымыз керек. Біз графтан екі бөлікті граф құрастыра аламыз , мұнда егер және тек қана графтың өлшемді сәйкестігі болса, онда графтың төбелері өзара қиылыспайтын жолдармен жабылады, онда жолдардың саны және жиектердің саны болады, мұнда графтың төбелерінің саны болып табылады. Сондықтан, мәселені екі бөлікті графтың ең үлкен сәйкестігін табу арқылы шешуге болады. Біз сәйкестік таптық және одан жабу құрастырдық деп есептейік. Егер екі төбе сәйкестікте сәйкес келсе, онда жиек жабуға кіреді. Жабудағы төбелердің екі кіріс және екі шығыс жиегі болмайды, сондықтан барлық жолдар төбелерде өзара қиылыспайды. Жабудың өлшемі екенін көрсету үшін бос жабудан бастаймыз және оны біртіндеп құрастырамыз. Жабуға төбе қосу үшін, оны қолданыстағы жолға қосуға немесе сол төбеден басталатын жаңа нөлдік ұзындықтағы жол құруға болады. Бірінші жағдай кез келген кезде қолданылады, егер және жабудағы кейбір жол төбеден басталатын болса, немесе және кейбір жол төбеде аяқталады. Екінші жағдай әрқашан қолданылады. Бірінші жағдайда жабудағы жиектердің жалпы саны 1-ге артады, ал жолдар саны өзгермейді; екінші жағдайда жолдар саны артады, ал жиектер саны өзгермейді. Енді барлық төбелерді жапқаннан кейін жабудағы жолдар мен жиектер санының қосындысы тең екендігі анық. Сондықтан, егер жабудағы жиектер саны болса, онда жолдар саны болады.
Then it can be shown that has a matching of size if and only if has a vertex disjoint path cover containing edges and paths, where is the number of vertices in Therefore, the problem can be solved by finding the maximum cardinality matching in instead. Assume we have found a matching of , and constructed the cover from it. Intuitively, if two vertices are matched in , then the edge is contained in Clearly the number of edges in is To see that is vertex disjoint, consider the following:
Each vertex in can either be non matched in , in which case there are no edges leaving in ; or it can be matched, in which case there is exactly one edge leaving in In either case, no more than one edge leaves any vertex in Similarly for each vertex in – if it is matched, there is a single incoming edge into in ; otherwise has no incoming edges in Thus no vertex has two incoming or two outgoing edges in , which means all paths in are vertex disjoint. To show that the cover has size , we start with an empty cover and build it incrementally. To add a vertex to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either and some path in the cover starts at , or and some path ends at The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all vertices, the sum of the number of paths and edges in the cover is Therefore, if the number of edges in the cover is , the number of paths is .
Жоғарғы қуаттылықпен ең үлкен ағын
Келіңіздер, бұл желі болсын. Әрбір түйінде қабырға сыйымдылығынан өзге сыйымдылық бар деп есептейік, яғни, ағын сыйымдылық шектеуін және ағын сақталуын қанағаттандырумен қатар, түйін сыйымдылығы шектеуін де қанағаттандыруы керек.
Басқаша айтқанда, түйін арқылы өтетін ағын мөлшері оның сыйымдылығынан аспауы тиіс. ағынының максималды мәнін табу үшін, мәселені бастапқы түсінігіндегі максималды ағын мәселесіне түрлендіре аламыз. Ол үшін, әрбір түйін екі түйінге – және – ауыстырылады, мұнда түйініне кіретін қабырғалар қосылады, ал түйінінен шығатын қабырғалар қосылады. Содан кейін және түйіндерін жалғайтын қабырғаға сыйымдылығы тағайындалады (4.4.1-суретті қараңыз). Осы кеңейтілген желіде түйін сыйымдылығы бойынша шектеу алынып тасталады, сондықтан мәселені бастапқы максималды ағын мәселесі ретінде қарастыруға болады.
s-тен t-ке дейінгі жолдардың ең көп саны
Бағытталған граф және екі төбе және берілгенде, -ден -ға бағытталған жолдардың максималды санын табу керек. Бұл мәселенің бірнеше түрі бар:
1. Жолдар жиектері бойынша бөлек болуы керек. Бұл мәселені максималды ағын мәселесіне түрлендіруге болады, үшін желі құру арқылы, мұнда және сәйкесінше бастапқы және аяқтағы нүктелер болып табылады, ал әр жиекке 1 сыйымдылық беріледі. Бұл желіде максималды ағын, егер жиектері бойынша бөлек жолдар болса ғана болады. 2. Жолдар тәуелсіз болуы керек, яғни төбелері бойынша бөлек ( және басқа). Біз төбелік сыйымдылықтары бар желі құра аламыз, мұнда барлық төбелердің және барлық жиектердің сыйымдылығы 1-ге тең. Онда максималды ағын мәні, -ден -ға бағытталған тәуелсіз жолдардың максималды санына тең болады. 3. Жолдар жиектері бойынша және/немесе төбелері бойынша бөлек болудан басқа, жолдардың ұзындығына да шектеу қойылады: біз ұзындығы дәл немесе ең көп дегенде болатын жолдарды ғана есептейміз. Бұл мәселенің көптеген түрлері NP-толық, -тың кішкентай мәндерінен басқа.
3. In addition to the paths being edge disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly , or at most Most variants of this problem are NP complete, except for small values of .
Жабылу проблемасы
Бағытталған графтың жабылуы – графтан ешқандай қабырға шықпайтын C төбелерінің жиыны. Жапқыш мәселесі – төбелері салмақталған бағытталған графтағы ең үлкен немесе ең кіші салмақты жабылуды табу есебі. Оны ең үлкен ағын мәселесіне келтіру арқылы полиномдық уақытта шешуге болады.
Әуе қатынасы компанияларының кестесі
Әуе тасымал саласындағы маңызды мәселе – ұшу экипаждарының кестесін жасау. Әуе тасымал компанияларының кестелеу мәселесін кеңейтілген максималды желілік ағынның қолданылуы ретінде қарастыруға болады. Бұл мәселенің кірістік деректері – F рейстер жиынтығы, ол әр рейстің қайдан және қашан ұшып кетуі және қондысы туралы ақпаратты қамтиды. Әуе тасымал кестелеуінің бір түріндегі мақсат – ең көп дегенде k экипажбен іске асырылатын кесте жасау. Бұл мәселені шешу үшін шектелген айналым деп аталатын айналым мәселесінің түрі қолданылады, ол желілік ағын мәселелерін жалпылайды және шеттік ағындарға төменгі шектеу қойылады. G = (V, E) желісін қарастырайық, мұнда s, t ∈ V – бастапқы және соңғы түйіндер. Әрбір i рейсінің бастапқы және соңғы нүктелері үшін V жиынына екі түйін қосылады: si түйіні – i рейсінің бастапқы нүктесі, ал di түйіні – i рейсінің соңғы нүктесі. Сонымен қатар, E жиынына келесі жиектер қосылады: s және әр si арасындағы сыйымдылығы [0, 1] жиек. Әрбір di және t арасындағы сыйымдылығы [0, 1] жиек. Әрбір si және di жұбы арасындағы сыйымдылығы [1, 1] жиек. Егер i рейсінің соңғы нүктесінен ақылға қонымды уақыт пен шығынмен sj бастапқы нүктесіне жетуге болады, онда di мен sj арасында сыйымдылығы [0, 1] жиек қосылады. s және t арасындағы сыйымдылығы [0, ∞] жиек. Аталған әдісте, s және t арасындағы G желісінде k ағын мәнін табу, F рейстер жиынтығы үшін ең көп дегенде k экипажмен іске асырылатын кесте табуға тең екені дәлелденеді. Әуе тасымал кестелеуінің тағы бір түрі – барлық рейстерді орындау үшін қажетті экипаждың ең аз санын табу. Бұл мәселенің шешімін табу үшін екі бөлікті график құрылады, онда әр рейстің A және B жиынында бір көшірмесі болады. Егер бір ұшақ i рейсінен кейін j рейсін орындай алса, онда i ∈ A, j ∈ B түйіндері қосылады. G' графындағы сәйкестік F рейсі үшін кесте құрады, ал осы графиктегі екі бөлікті сәйкестіктің максималды саны экипаждың ең аз санымен әуе тасымал кестесін құрады.
An edge with capacity [0, 1] between s and each si. An edge with capacity [0, 1] between each di and t.
An edge with capacity [1, 1] between each pair of si and di. An edge with capacity [0, 1] between each di and sj, if source sj is reachable with a reasonable amount of time and cost from the destination of flight i. An edge with capacity [0, ∞] between s and t.
In the mentioned method, it is claimed and proved that finding a flow value of k in G between s and t is equal to finding a feasible schedule for flight set F with at most k crews. Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph is created where each flight has a copy in set A and set B. If the same plane can perform flight j after flight i, i∈A is connected to j∈B. A matching in G' induces a schedule for F and obviously maximum bipartite matching in this graph produces an airline schedule with minimum number of crews.
Ұзартулар
1. Ең төменгі құн ағыны мәселесінде әр қабырғаның (u,v) сыйымдылығынан өзге, auv құн коэффициенті де болады. Егер қабырға арқылы өтетін ағын fuv болса, онда жалпы құн auvfuv болады. Белгілі бір көлемді d ағынды ең төменгі құнмен табу қажет. Көптеген жағдайларда құн коэффициенттері оң немесе теріс болуы мүмкін. Бұл мәселені шешу үшін түрлі полиномиалды уақыт алгоритмдері бар. 2. Максималды ағын мәселесін дизъюнктивті шектеулермен толықтыруға болады: теріс дизъюнктивті шектеу, екі қабырға жұбының бір уақытта нөлден өзгеше ағыны болуы мүмкін емес екенін көрсетеді; оң дизъюнктивті шектеу, екі қабырға жұбының біреуінде кем дегенде нөлден өзгеше ағын болуы керек екенін көрсетеді. Теріс шектеулер болған жағдайда, тіпті қарапайым желілер үшін де мәселе күрделі NP қиындығына жатады. Оң шектеулер болған жағдайда, бөлшектік ағындарға рұқсат берілсе, мәселе полиномиалды, бірақ ағындар бүтін санмен болған жағдайда күрделі NP қиындығына жатуы мүмкін.