Grafu ina vipeo na kingo. Vipeo vimeunganishwa na kingo kulingana na mali fulani - uhusiano wa matukio, ambayo hufafanua seti ya kingo. Katika kesi hii, vitanzi na wima zilizotengwa zinaweza kuunda.
Maagizo
Hatua ya 1
Wacha seti ya kingo za grafu itolewe na uhusiano ambao inawezekana kuteka makali kutoka kwa vertex moja hadi nyingine hutolewa. Kama mfano, seti ya vipeo {1, 2, 3, 4, 5, 6, 7, 8}, vipeo viwili x na y viko katika uwiano x + y <8.
Hatua ya 2
Jenga matrix ya karibu ya vertex. Ili kufanya hivyo, jenga meza ya mraba, idadi ya safu na nguzo kwenye jedwali inafanana na idadi ya vipeo. Kisha weka 1 kwenye makutano ya safu ya i-th na safu ya j-th ikiwa wima i na j zinakidhi uwiano uliopewa. Weka 0 kwenye makutano ya safu ya i-th na safu ya j-th ikiwa uwiano wa vitu vinavyolingana haukutimizwa.
Katika mfano wetu, mstari wa kwanza umejazwa kama ifuatavyo:
1 + 1 <8, kwa hivyo kuna 1 kwenye makutano ya safu ya 1 na safu ya 1
1 + 2 <8, tena 1
1 + 3 <8, tena 1
1 + 7 <8, usawa usio sahihi, kwa hivyo kipengee hiki cha meza kitakuwa 0
1 + 8 <8, tena 0
Hatua ya 3
Ili kujua idadi ya kingo, hesabu idadi ya zile zilizo kwenye tumbo la karibu bila kuiga kingo.
Kwa mfano, tumbo lenye ulinganifu lilipatikana, kwa hivyo tulihesabu kwanza zile zilizo juu ya ulalo kuu wa tumbo (iliyowekwa alama ya hudhurungi), na kisha zile zilizo kwenye ulalo kuu (uliowekwa alama nyekundu). Jumla ya mbavu ni 12.
Hatua ya 4
Jenga matrix ya matukio (kingo). Ili kufanya hivyo, chora meza, idadi ya safu ndani yake ni sawa na idadi ya vipeo kwenye grafu, na idadi ya nguzo ni sawa na idadi ya kingo. Weka vitengo kwenye mistari hiyo ambayo itaunganishwa na makali. Viunga vinavyoongoza kutoka kwa vertex hadi hiyo huitwa matanzi na huongezwa hadi mwisho wa tumbo. Katika safu zinazofanana na matanzi, kuna kitengo kimoja tu, tofauti na kingo zingine.
Hatua ya 5
Sasa chora grafu. Weka vipeo kwenye karatasi kwa njia yoyote na uziunganishe na kingo ukitumia meza zilizojengwa. Vertices ambazo hazijaunganishwa na kingo huitwa pekee.
