அதிகபட்ச நெட்வொர்க் ஃப்ளோ அல்காரிதம். அதிகபட்ச ஓட்டத்தைக் கண்டறிவதற்கான அல்காரிதம்

ஃபோர்டு-ஃபுல்கர்சன் வழிமுறையைப் பயன்படுத்தி போக்குவரத்து நெட்வொர்க்கில் அதிகபட்ச ஓட்டத்தைக் கண்டறிவதில் உள்ள சிக்கலைத் தீர்த்து, நெட்வொர்க் பிரிவை உருவாக்கவும் எஸ்.
ஆரம்ப தரவு:
கொடுக்கப்பட்ட நெட்வொர்க் S(X,U)
- பிணையத்தின் ஆதாரம்; - நெட்வொர்க் வடிகால், அங்கு ∈X; ∈X.
வில் திறன் மதிப்புகள் ஆர்க் நோக்குநிலையின் திசையில் குறிப்பிடப்படுகின்றன: குறியீட்டு i முதல் குறியீட்டு j வரை.

r = 39; ஆர் = 44; ஆர் = 33; ஆர் = 53; ஆர் = 10;
ஆர் = 18; r = 95; ஆர் = 16; ஆர் = 23; ஆர் = 61;
ஆர் = 81; ஆர் = 71; ஆர் = 25; r = 15; ஆர் = 20

1. நெட்வொர்க்கில் பூஜ்ஜிய ஓட்டத்தை அமைக்கவும் (அனைத்து வளைவுகளிலும் ஓட்ட மதிப்பு 0 ஆகும்). ஃப்ளோ ஜீரோ என்பது நெட்வொர்க்கில் அனுமதிக்கப்பட்ட தொடக்க ஓட்டமாகும். ஒவ்வொரு வளைவின் ஓட்ட மதிப்பு வில் திறன் அடைப்புக்குறிகளுக்கு வெளியே குறிக்கப்படும்.). "0" க்கு சமமான ஓட்ட மதிப்பு குறிப்பிடப்படவில்லை.
2. வெர்டெக்ஸ் x0 இலிருந்து வெர்டெக்ஸ் x7 வரை செல்லும் நெட்வொர்க்கில் ஒரு பாதையைத் தேர்ந்தெடுக்கவும் (தன்னிச்சையாக)
X0-X1-X4-X6-X7
3. கண்டுபிடி இந்த அளவு ஓட்டத்தை அதிகரிக்கவும். எட்ஜ் X1-X4 கருதப்பட்டதாகக் குறிக்கப்பட்டுள்ளது.


4. மற்றொரு பாதையைத் தேர்வு செய்யவும், எடுத்துக்காட்டாக: X0-X2-X5-X7, கண்டுபிடி இந்த அளவு ஓட்டத்தை அதிகரிக்கவும். எட்ஜ் X0-X2 கருதப்பட்டதாகக் குறிக்கப்பட்டுள்ளது.


5. மற்றொரு பாதையைத் தேர்வு செய்யவும், எடுத்துக்காட்டாக: X0-X3-X2-X5-X7, இந்த அளவு மூலம் ஓட்டத்தைக் கண்டுபிடித்து அதிகரிக்கவும். எட்ஜ் X3-X2 கருதப்பட்டதாகக் குறிக்கப்பட்டுள்ளது.


6. X0 இலிருந்து X7 வரையிலான பாதைகள் எதுவும் இல்லை, ஓட்டத்தின் அதிகரிப்பை சுருக்கமாகக் கூறுவோம்: 25+10+20=55.
முடிவு: அதிகபட்ச ஓட்டம் 55.

2) நெட்வொர்க் S இன் ஒரு பகுதியை உருவாக்கவும்.
"வெர்டெக்ஸ் மார்க்கிங்" செயல்முறை.
ஆரம்ப நிலை: அனைத்து செங்குத்துகளும் லேபிளிடப்படவில்லை.
X0 முனைக்கு ஒரு லேபிள் ஒதுக்கப்பட்டுள்ளது. வில் செறிவூட்டப்படாத அனைத்து செங்குத்துகளுக்கும் மதிப்பெண்கள் ஒதுக்கப்படுகின்றன (சிவப்பு வட்டங்கள்)


நாங்கள் குறைந்தபட்ச வெட்டு வளைவுகளை வரையறுக்கிறோம்: இவை வளைவுகள், அவற்றின் தொடக்கங்கள் குறிக்கப்பட்ட முனைகளிலும், அதன் முனைகள் பெயரிடப்படாத செங்குத்துகளிலும் இருக்கும்.
இவை வளைவுகள்:
இதனால், இந்த நெட்வொர்க்கின் குறைந்தபட்ச வெட்டு
அதிகபட்ச ஓட்ட மதிப்பின் கணக்கீடு

ஒரு இயக்கப்பட்ட வரைபடம் கொடுக்கப்பட வேண்டும் ஜி= , இதில் ஒவ்வொரு பரிதியின் திசை vÎVஓட்டத்தின் திசையைக் குறிக்கிறது (எடுத்துக்காட்டாக, கார்களின் ஓட்டம்), செயல்திறன்ஒவ்வொரு வளைவும் சமம் d(v)பல சிகரங்களில் ஈஇரண்டு முனைகள் முன்னிலைப்படுத்தப்படுகின்றன டிமற்றும் கள். உச்சி டிஓட்டத்தின் ஆதாரம், கள்- வடிகால். உச்சியில் இருந்து அனுப்பக்கூடிய அதிகபட்ச ஓட்டத்தை தீர்மானிக்க இது தேவைப்படுகிறது டிவி கள் .

மூலம் குறிப்போம் x(v)ஒரு வளைவுடன் நகரும் ஓட்டத்தின் அளவு v. என்பது வெளிப்படையானது

0 £ x(v) £ d(v) , vÎV . (6. 1)

ஒவ்வொரு சிகரத்திலும் iÎE\(t,s)உள்வரும் ஓட்டத்தின் அளவு வெளிச்செல்லும் ஓட்டத்தின் அளவிற்கு சமம், அதாவது. சமத்துவம் உண்மை

(x(v)|i О V + (i))= (x(v)| iО V - (i))

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

மேலே டி

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

உச்சிக்கு s

(x(v)| iО V + (i)) -(x(v)¦ i О V - (i))= கே.(6.4)

அளவு கேஉச்சியை விட்டு வெளியேறும் ஓட்டத்தின் அளவு டிமற்றும் மேல் நுழைகிறது கள்.

தீர்மானிக்க வேண்டும்

Q® அதிகபட்சம்(6.5)

கட்டுப்பாடுகளின் கீழ் (6.1-6.4).

அளவுகள் Q, x(v) , vÎV,திருப்திகரமான கட்டுப்பாடுகள் (6.1-6.4) நெட்வொர்க்கில் ஒரு ஓட்டத்தை அழைப்போம், மேலும் அவை மதிப்பை அதிகப்படுத்தினால் கே, பின்னர் அதிகபட்ச ஓட்டம். மதிப்புகளைப் பார்ப்பது எளிது Q=0, x(v)=0, vÎV, நெட்வொர்க்கில் ஒரு ஓட்டம்.

பிரச்சனை (6.1-6.5) ஒரு பிரச்சனை நேரியல் நிரலாக்கமேலும் இது சிம்ப்ளக்ஸ் முறை அல்காரிதம்களைப் பயன்படுத்தி தீர்க்கப்படும்.

E என்ற செங்குத்துகளின் தொகுப்பை E1 மற்றும் E2 என்ற இரு இணை பாகங்களாகப் பிரிப்போம். tÎE1, sÎE2. வெட்டு மூலம் V(E1,E2), பிரித்தல் டிமற்றும் கள்நாங்கள் தொகுப்பை அழைப்போம் V(E1,E2)ÌVஒவ்வொரு வளைவுக்கும் v О V(E1,E2)அல்லது h1(v)OE1மற்றும் h2(v)OE2, அல்லது h1(v)OE2மற்றும் h2(v)OE1.

தொகுப்பைப் பிரிப்போம் V(E1,E2)இரண்டு பகுதிகளாக V(E1,E2,+),V(E1,E2,-)பின்வருமாறு:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1மற்றும் h2(v)OE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1மற்றும் h1(v)OE2)

வெட்டலின் செயல்திறன் திறனை நாம் அழைப்போம்

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

பின்வருபவை உண்மைதான்

தேற்றம் 1. (அதிகபட்ச ஓட்டம் மற்றும் குறைந்தபட்ச வெட்டு பற்றி).

எந்த நெட்வொர்க்கிலும், மூலத்திலிருந்து அதிகபட்ச ஓட்டம் டிபங்கு வைக்க கள்குறைந்தபட்ச செயல்திறனுக்கு சமம் Q(E1,E2)அனைத்து வெட்டுக்களுக்கு மத்தியில் V(E1,E2), செங்குத்துகளை பிரிக்கிறது டிமற்றும் கள்.

அதிகபட்ச ஓட்டத்தில் என்பதை நினைவில் கொள்க

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

விடுங்கள் Q, x(v), vÎV, -சில பிணைய ஓட்டம், வரிசை

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

செங்குத்துகளை இணைக்கும் சங்கிலி டிமற்றும் கள். இந்த சங்கிலியில் உச்சியில் இருந்து இயக்கத்தின் திசையை அமைப்போம் டிசெய்ய கள். பரிதி v(j)இந்த சங்கிலியிலிருந்து அதன் திசையானது இயக்கத்தின் திசையுடன் ஒத்துப்போகும் பட்சத்தில் நேர்கோடு என்று அழைக்கப்படுகிறது டிசெய்ய கள், மற்றும் தலைகீழ் இல்லையெனில். இந்த சங்கிலியை பாதை என்று அழைப்போம் அதிகரிக்கும் ஓட்டம், நேரான வளைவுகள் என்றால் vசங்கிலிகள் x(v)< d(v) மற்றும் தலைகீழாக x(v) > 0. இந்த சுற்று வழியாக கூடுதல் ஓட்டம் செல்ல முடியும் கேஇருந்து டிசெய்ய கள்அளவு q = நிமிடம்(q1,q2),எங்கே q1=நிமிடம் (d(v) -x(v)), சங்கிலியின் அனைத்து நேரான வளைவுகளிலும் குறைந்தபட்சம் எடுக்கப்படுகிறது, q1=நிமிடம் (x(v)), சங்கிலியின் அனைத்து தலைகீழ் வளைவுகளிலும் குறைந்தபட்சம் எடுக்கப்படுகிறது.

தேற்றம் 2.

ஓட்டம் Q, x(v) , vÎV, ஓட்டத்தை அதிகரிக்க வழி இல்லை என்றால் மட்டுமே அதிகபட்சம்.

நெட்வொர்க்கில் அதிகபட்ச ஓட்டத்தின் சிக்கலைத் தீர்ப்பதற்கான முன்மொழியப்பட்ட அல்காரிதம், இதிலிருந்து ஓட்டத்தை அதிகரிப்பதற்கான வழியைக் கண்டுபிடிப்பதை அடிப்படையாகக் கொண்டது. டிவி கள், இது வெர்டெக்ஸ் லேபிள்களை ஒழுங்குபடுத்தும் செயல்முறையை அடிப்படையாகக் கொண்டது. என்று சொல்லலாம்

உச்சி iஒரு அடையாளத்துடன் குறிக்கப்பட்டது q(i)>0, மற்றும் நேராக ஆர்க் ஆர்க் அறியப்படுகிறது v(i), இதன் மூலம் இந்த ஓட்டம் வந்தது அல்லது குறிக்கப்பட்டுள்ளது , அளவு சில கூடுதல் ஓட்டம் என்றால் q(i)>0, மற்றும் தலைகீழ் ஆர்க் அறியப்படுகிறது v(i), இந்த ஓட்டம் நுழைந்தது;

vertex i அதன் அனைத்து அண்டை முனைகளும் குறிக்கப்பட்டால் பார்க்கப்படும்.

உச்சி s குறிக்கப்பட்டால், ஓட்டத்தை அளவு அதிகரிக்க ஒரு பாதை கண்டறியப்பட்டுள்ளது கே, இது இந்த பாதையில் கடந்து செல்கிறது. அல்காரிதத்தை விவரிக்க நமக்கு ஒரு வரிசையும் தேவை SPW, அவை குறிக்கப்பட்ட வரிசையில் குறிக்கப்பட்ட செங்குத்துகளின் எண்களைக் கொண்டுள்ளது. C1- வரிசையில் உள்ள எண் SPWபார்த்த உச்சம், C2- இந்த வரிசையில் கடைசியாக குறிக்கப்பட்ட உச்சியின் எண்ணிக்கை.

இந்த கையேடு படிப்பை எடுக்கும் மாணவர்களுக்காக வடிவமைக்கப்பட்டுள்ளது தனித்த கணிதம்மற்றும்/அல்லது வரைபடக் கோட்பாடு.

அதன் உதவியுடன் நீங்கள் "நெட்வொர்க்கில் அதிகபட்ச ஓட்டம் மற்றும் குறைந்தபட்ச வெட்டு" என்ற தலைப்பில் தேர்ச்சி பெறுவீர்கள்.

• இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம்.=|உங்களிடம் MATLAB இருந்தால், இந்தப் பக்கத்திற்குச் செல்லவும்: கணக்கீட்டு ஸ்கிரிப்டில் (நிரல்) தலையிட உங்களுக்கு வாய்ப்பு உள்ளது. இங்கே, நெட்வொர்க்கில் அதிகபட்ச ஓட்டத்தின் சிக்கல் அதை நேரியல் நிரலாக்க சிக்கலாகக் குறைப்பதன் மூலம் தீர்க்கப்படுகிறது.பின்வரும் குறியீட்டை அறிமுகப்படுத்துவோம்:
• n=|ஈவி
• | - வரைபட அளவு (செங்குத்துகளின் எண்ணிக்கை); மீ இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம்.× n| - வரைபடம் கார்டினாலிட்டி (விளிம்புகளின் எண்ணிக்கை); ஏ− அளவிலான நெட்வொர்க் டிகிராப்பின் நிகழ்வு மேட்ரிக்ஸ் i; அதன் ஒவ்வொரு உறுப்பு ஒரு ஐ.கே=1 என்றால் ஏ- மேல் வெளியே வருகிறது iகே ஒரு ஐ.கே-நான் வில்; ஏ=−1, இருந்தால்
• கள்வது உச்சி நுழைகிறது
• டி-நான் வில்; மற்றும்
• மற்ற சந்தர்ப்பங்களில் =0; அத்தகைய மேட்ரிக்ஸின் ஒவ்வொரு நெடுவரிசையிலும் சரியாக ஒன்று உள்ளது, ஒன்று கழித்தல் ஒன்று, மீதமுள்ளவை பூஜ்ஜியங்கள்;நெட்வொர்க்கின் மூல உச்சியின் எண்; இந்த உச்சியில் இருந்து வளைவுகள் மட்டுமே வெளிப்பட வேண்டும், மேலும் வேறு எந்த முனையும் மூலத்திலிருந்து அடையக்கூடியதாக இருக்க வேண்டும்; − கள் | - வரைபட அளவு (செங்குத்துகளின் எண்ணிக்கை); − பிணைய சிங்க் உச்சியின் எண்; இந்த உச்சியில் வளைவுகள் மட்டுமே நுழைய வேண்டும், மேலும் ஒரு வடிகால் வேறு எந்த முனையிலிருந்தும் அடையக்கூடியதாக இருக்க வேண்டும்;
• மற்ற சந்தர்ப்பங்களில் =0; அத்தகைய மேட்ரிக்ஸின் ஒவ்வொரு நெடுவரிசையிலும் சரியாக ஒன்று உள்ளது, ஒன்று கழித்தல் ஒன்று, மீதமுள்ளவை பூஜ்ஜியங்கள்;டி − டிஅ | - வரைபட அளவு (செங்குத்துகளின் எண்ணிக்கை); கள்
• | - வரைபட அளவு (செங்குத்துகளின் எண்ணிக்கை);;அது மட்டுமே கொண்டிருக்க வேண்டும், ஏனெனில் மூலத்திலிருந்து வளைவுகள் மட்டுமே வெளிப்பட வேண்டும்; | - வரைபட அளவு (செங்குத்துகளின் எண்ணிக்கை); நெட்வொர்க் டிகிராஃபின் நிகழ்வு மேட்ரிக்ஸின் -வது வரிசை கள்; டிஅதில் மைனஸ் மட்டுமே இருக்க வேண்டும், ஏனெனில் வளைவுகள் மட்டுமே வடிகால் நுழைய வேண்டும்;
• செயின்ட் − நெட்வொர்க் டிகிராஃபின் நிகழ்வு மேட்ரிக்ஸ் nஅதிலிருந்து தூக்கி எறியப்பட்டவர்களுடன் வது மற்றும்வது கோடுகள்; ஒரு ஐ.கேஇ
• − நெடுவரிசை திசையன் நீளம் − நெட்வொர்க் டிகிராஃபின் நிகழ்வு மேட்ரிக்ஸ் nஅதிலிருந்து தூக்கி எறியப்பட்டவர்களுடன் ; அதன் ஒவ்வொரு உறுப்புகளிலும்இ கே ஒரு ஐ.கேஉள்ளே ஓட்டத்தின் அளவு இருக்கும்

வது வில்;

மூலத்திலிருந்து வெளியேறும் மொத்த ஓட்டம் (1) அதிகரிக்கப்படுகிறது. மேலும், எந்த இடைநிலை உச்சியிலும் உள்வரும் ஓட்டம் வெளிச்செல்லும் ஓட்டத்திற்கு சமமாக இருக்கும் (2), மற்றும் வளைவுகளின் திறன் குறைவாக உள்ளது (3).

அதிகபட்ச ஓட்டம் பிரச்சனைக்கு இரட்டை பிரச்சனை குறைந்தபட்ச வெட்டு பிரச்சனை. ஒரு குறைந்தபட்ச வெட்டு உருவாக்க, நீங்கள் இருமைத் தேற்றங்களைப் பயன்படுத்தலாம். தேவை:

• பிணைய வரைபடத்திலிருந்து அனைத்து காலியானவற்றையும் அகற்றவும் ( வது மற்றும்= 0) மற்றும் நிறைவுற்ற ( வது மற்றும் = ; அதன் ஒவ்வொரு உறுப்புகளிலும்) வளைவுகள்;
• மீதமுள்ள வரைபடத்தின் இணைக்கப்பட்ட கூறுகளைக் கண்டறியவும்;
• அத்தகைய இரண்டு கூறுகள் இருந்தால், நிராகரிக்கப்பட்ட வளைவுகள் குறைந்தபட்ச வெட்டு கொடுக்கின்றன;
• இரண்டுக்கும் மேற்பட்ட இணைக்கப்பட்ட கூறுகள் தோன்றினால், நெட்வொர்க் டிகிராஃப் பல குறைந்தபட்ச வெட்டுக்களைக் கொண்டுள்ளது (தொடர்புடைய நேரியல் நிரலாக்கச் சிக்கல் சீரழிந்தது).

சீரழிந்த பிரச்சனைக்கு, மூலத்திற்கு மிக நெருக்கமான முதல் குறைந்தபட்ச வெட்டு இந்தப் பக்கத்தில் கட்டமைக்கப்பட்டுள்ளது.

க்கு சரியான செயல்பாடுஇந்தப் பக்கத்துடன் உங்கள் உலாவி ஸ்கிரிப்ட்களை ஆதரிக்க வேண்டும் ஜாவா ஸ்கிரிப்ட். அவற்றை இயக்கவும்.

கீழே உள்ள உள்ளீடு பகுதிகளில் ஆரம்ப தரவை உள்ளிடவும். உங்களுக்குத் தேவையான முதல் பகுதியில் (இன்னும் துல்லியமாக, உங்களால் முடியும்) நெட்வொர்க்கின் ஒரு வரைபடத்தை வரைய செங்குத்துகளின் ஆயங்களை உள்ளிடவும். அவை மேட்ரிக்ஸ் வடிவத்தில் குறிப்பிடப்படுகின்றன இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம்.×2: முதல் நெடுவரிசையில் - xவது ஒருங்கிணைப்புகள், இரண்டாவது - இல் ஒய்-இ. எண்களை முழு எண்களாக, தசம புள்ளியுடன் அல்லது அதிவேக வடிவத்தில் குறிப்பிடலாம். இடைவெளிகளுடன் தனி எண்கள். இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம்.இந்த உள்ளீட்டுப் பகுதியில் உள்ள மொத்த வரிகளின் எண்ணிக்கை டிக்ராவின் அளவை தீர்மானிக்கிறது இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம்.- முனைகளின் எண்ணிக்கை. இந்த ஆரம்ப தரவு (வெர்டெக்ஸ் ஆயத்தொலைவுகள்) விருப்பமானது: அவை குறிப்பிடப்படவில்லை என்றால், பிணைய விளக்கப்படம் சரியானதாக வரையப்படும்.

-gon, மற்றும் செங்குத்துகளின் எண்ணிக்கை அடுத்த உள்ளீட்டு பகுதியில் உள்ள அதிகபட்ச உச்சி எண்ணால் தீர்மானிக்கப்படும். nஅடுத்த உள்ளீடு பகுதியில், இடது பகுதி தேவைப்படுகிறது. இது பிணைய வரைபடத்தின் கட்டமைப்பை வரையறுக்கிறது. ஒரு வரைபடத்தில் உள்ள ஒவ்வொரு வளைவும் இரண்டு செங்குத்துகளை இணைக்கிறது. இந்த செங்குத்துகளின் எண்கள் மேட்ரிக்ஸ் வடிவத்தில் குறிப்பிடப்படுகின்றனஇரண்டாவது உள்ளீட்டு பகுதியின் இடது பக்கத்தில் ×2. ஒவ்வொரு வரியிலும், வளைவின் 1 வது உச்சி (வால், மூல) முதலில் குறிப்பிடப்படுகிறது, பின்னர், ஒரு இடைவெளி வழியாக, வளைவின் 2 வது உச்சி (முனை, வடிகால்) குறிப்பிடப்படுகிறது. இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம்.இந்த நெடுவரிசைகள் இருக்க வேண்டும் nஇயற்கை எண்கள்

விநியோக நெட்வொர்க்கில் தயாரிப்புகளின் பகுத்தறிவு விநியோகத்தைத் திட்டமிடும்போது, ​​வாடிக்கையாளர் தேவைகள் மற்றும் சக்தியுடன் சேனல் திறனை ஒருங்கிணைக்க வேண்டியது அவசியம். உற்பத்தி நிறுவனம். இந்த வகை சிக்கல்கள் அதிகபட்ச ஓட்டத்தைக் கண்டறிவதன் மூலம் தீர்க்கப்படுகின்றன.

விநியோக வலையமைப்பைக் கவனியுங்கள் (படம் 4.21), இதில் புள்ளிகள் 0 முன்னிலைப்படுத்தப்பட்டுள்ளது (நுழைவு, எடுத்துக்காட்டாக, கிடங்கு முடிக்கப்பட்ட பொருட்கள்உற்பத்தியாளர்) மற்றும் n (வெளியேறும், விநியோக மையங்கள், மொத்த மற்றும் சில்லறை நிறுவனங்களின் கிடங்குகள், நுகர்வோர்) மற்றும் ஒவ்வொரு வில் (பிரிவு) இணைக்கும் புள்ளிகள் i மற்றும் j, எண் dij > 0 தொடர்புடையது, அழைக்கப்படுகிறது செயல்திறன் வளைவுகள். செயல்திறன் மதிப்பு என்பது ஒரு யூனிட் நேரத்திற்கு தொடர்புடைய வளைவுடன் செல்லக்கூடிய அதிகபட்ச அனுமதிக்கப்பட்ட பொருள் ஓட்டத்தை வகைப்படுத்துகிறது.

அரிசி. 4.21.

ஒரு வில் வழியாக செல்லும் பொருட்களின் அளவு i செய்ய ஜே , நாம் அதை வளைவுடன் ஒரு ஓட்டம் என்று அழைப்போம் ( i ,ஜே ) மற்றும் ஆல் குறிக்கப்படுகிறது. என்பது வெளிப்படையானது

நெட்வொர்க்கின் இடைநிலைப் புள்ளியில் நுழையும் முழுப் பொருள் ஓட்டமும் அதிலிருந்து முழுமையாக வெளியேற வேண்டும் என்பதை நாம் கணக்கில் எடுத்துக் கொண்டால், நாம் பெறுகிறோம்

நம்மிடம் உள்ள உள்ளீடு மற்றும் வெளியீட்டில் உள்ள ஓட்டங்களின் சமத்துவத்தின் இயல்பான தேவையிலிருந்து

நாம் Z இன் மதிப்பை நெட்வொர்க்கில் உள்ள ஓட்டத்தின் மதிப்பு என்று அழைப்போம் மற்றும் மேலே உள்ள நிபந்தனைகளுக்கு உட்பட்டு Z ஐ அதிகப்படுத்துவதில் சிக்கலை ஏற்படுத்துவோம்.

அதிகபட்ச ஓட்டத்தைக் கண்டறிவது, குறைந்தபட்ச வெட்டின் செயல்திறனைக் கண்டறிவதாகும்.

மேட்ரிக்ஸ் வடிவத்தில் உலகளாவிய தேடல் அல்காரிதத்தை கருத்தில் கொள்வோம்.

அல்காரிதத்தின் ஆரம்ப நிலை ஒரு மேட்ரிக்ஸை உருவாக்குவதைக் கொண்டுள்ளது டி 0, இதில் செயல்திறன் மதிப்புகள் உள்ளிடப்படுகின்றன (நோக்குநிலையற்ற வளைவுக்கு நாம் அணி உறுப்புகளின் சமச்சீர் மதிப்புகளை எடுத்துக்கொள்கிறோம்).

வழிமுறையின் முக்கிய படிகள் ஒரு குறிப்பிட்ட பாதையை கண்டுபிடித்து இந்த பாதையில் ஓட்டத்தை சரிசெய்வதாகும்.

ஒரு பாதையைக் கண்டுபிடிக்கும் போது, ​​​​குறிக்கும் செயல்முறையைப் பயன்படுத்துகிறோம். மேட்ரிக்ஸின் பூஜ்ஜிய வரிசை மற்றும் நெடுவரிசையை * குறியீட்டுடன் குறிக்கிறோம் (நெட்வொர்க் உள்ளீடு). நாம் தேடும் 0 வது வரியில், தொடர்புடைய நெடுவரிசைகளை குறியீடுகளுடன் குறிக்கவும்

மற்றும் நெடுவரிசை லேபிள்களை வரிசைகளுக்கு நகர்த்தவும். பின்னர் நாம் ith குறிக்கப்பட்ட வரிசையை எடுத்து, அதில் குறியிடப்படாத நெடுவரிசையைத் தேடுகிறோம், அதனுடன் நாம் குறியீட்டு லேபிள்களுடன் பொருந்துகிறோம்

நெடுவரிசை லேபிள்களை வரிசைகளுக்கு மாற்றுவோம், மேலும் n வது நெடுவரிசை குறிக்கப்படும் வரை இந்த செயல்முறையைத் தொடரவும்.

பின்னர், குறியீடுகளைப் பயன்படுத்தி, η-வது உச்சிக்கு வழிவகுத்த பாதையைக் கண்டுபிடித்து, பாதையின் வளைவுகளின் (மேட்ரிக்ஸ் கூறுகள்) திறனைக் குறைக்கிறோம் உங்களிடம் MATLAB இருந்தால், இந்தப் பக்கத்திற்குச் செல்லவும்: கணக்கீட்டு ஸ்கிரிப்டில் (நிரல்) தலையிட உங்களுக்கு வாய்ப்பு உள்ளது. இங்கே, நெட்வொர்க்கில் அதிகபட்ச ஓட்டத்தின் சிக்கல் அதை நேரியல் நிரலாக்க சிக்கலாகக் குறைப்பதன் மூலம் தீர்க்கப்படுகிறது. n மற்றும் சமச்சீர் கூறுகளை அதே அளவு அதிகரிக்கவும்.

இந்த செயல்முறை குறிக்கும் வரை தொடர்கிறது இந்த கையேட்டில் இருந்து நேரடியாக, உங்கள் கணினியில் MATLAB இல்லாவிட்டாலும், உங்கள் ஐடியைக் கணக்கிடலாம். -டாப்ஸ் சாத்தியமற்றதாக ஆகாது.

அசல் மேட்ரிக்ஸில் இருந்து கழிப்பதன் மூலம் அதிகபட்ச ஃப்ளக்ஸைக் கண்டறியலாம் டி 0, திறன் மேட்ரிக்ஸின் மேற்கண்ட திருத்தத்திற்குப் பிறகு பெறப்பட்டது:

எடுத்துக்காட்டு 4.4

உற்பத்தி மாஸ்கோவில் அமைந்துள்ளது. தயாரிப்புகளை விநியோகிக்க, நிறுவனம் பல்வேறு நிலைகளில் விநியோக மையங்கள் மூலம் நிறுவனத்துடன் பணிபுரியும் இடைத்தரகர்களை ஈர்க்கிறது. ரஷ்யாவின் ஐரோப்பிய பகுதியில் மொத்த விற்பனை நிறுவனம் 1 உள்ளது, இது மத்திய விநியோக மையத்தால் சேவை செய்யப்படுகிறது. மொத்த விற்பனை நிறுவனம் 2 இல் இயங்குகிறது வெளிநாட்டிற்கு அருகில்(உக்ரைன், பெலாரஸ்) மற்றும் ஒரு பிராந்திய விநியோக மையத்தால் வழங்கப்படுகிறது. நிறுவனம் உள்ளூர் சந்தையில் (மாஸ்கோ மற்றும் மாஸ்கோ பிராந்தியம்) அதன் சொந்த வாடிக்கையாளர்களைக் கொண்டுள்ளது - நகர விநியோக மையத்திலிருந்து பொருட்களைப் பெறும் சில்லறை விற்பனையாளர்கள். பிராந்திய மற்றும் நகர விநியோக மையங்கள் மத்திய விநியோக மையத்தில் இருந்து மீட்டெடுக்கப்பட்டுள்ளன.

விநியோக நெட்வொர்க்கின் ஒரு பகுதியை முன்னிலைப்படுத்துவோம்:

• ஒரு உற்பத்தி நிறுவனத்தின் முடிக்கப்பட்ட பொருட்களின் கிடங்கு;
• மத்திய விநியோக மையம்;
• பிராந்திய விநியோக மையம்;
• நகர விநியோக மையம்;
• இரண்டு மொத்த விற்பனை நிறுவனங்கள்;
• நிறுவனத்திற்கு சொந்தமான சில்லறை விற்பனை நிலையம்;
• நுகர்வோர்.

அரிசி. 4.22.

விநியோக நெட்வொர்க்கின் ஒவ்வொரு இணைப்பையும் ஒரு எண்ணுடன் நியமிப்போம், மேலும் திறனை வளைவுகளுக்கு மேலே வைப்போம். செயல்திறன் திறன், இணைப்பின் வகையைப் பொறுத்து, உற்பத்தி திறனின் அளவு, நுகர்வோரின் திட்டமிடப்பட்ட தேவை (தேவை) மற்றும் சந்தை திறன் ஆகியவற்றின் அடிப்படையில் வெளிப்படுத்தப்படலாம்.

தயாரிப்பு விநியோக நெட்வொர்க் வரைபடம் படத்தில் காட்டப்பட்டுள்ளது. 4.23. ஒரு மேட்ரிக்ஸை உருவாக்குவோம் டி 0, விநியோக நெட்வொர்க் இணைப்புகளின் செயல்திறன் திறன்களின் மதிப்புகளை உள்ளிடுகிறோம் (படம் 4.24).

அரிசி. 4.23.

அரிசி. 4.24.

பூஜ்ஜிய வரிசையில் இருந்து நாம் செங்குத்துகளை (வரிசைகள்-நெடுவரிசைகள்) 1, 2 மற்றும் 3 குறியீடுகளுடன் μ = 0 மற்றும் வி, 30.10 மற்றும் 10 க்கு சமம்.

குறிக்கப்பட்ட வரி 1 இலிருந்து, 4 மற்றும் 5 குறியீடுகளுடன் μ = 1 மற்றும் V4 = நிமிடம் (30,15) = 15, V5 = நிமிடம் (30,10) = 10 எனக் குறிக்கவும்.

வரி 3 இலிருந்து நாம் உச்சி 6 ஐக் குறிக்கிறோம், இறுதியாக, வரி 4 இலிருந்து - உச்சி 7 (படம் 4.25).

அரிசி. 4.25

μ வழியாகத் திரும்பிச் செல்வதன் மூலம், பாதையைக் காண்கிறோம்: 4 முதல் 7 வரை, 1 முதல் 4 வரை, 0 முதல் 1 வரை; சரிசெய்யும் கூறுகள் டி 0 ஒரு ஓட்ட மதிப்பு V7 = 15.

அடுத்த படி ஓட்டம் 5 (படம் 4.26) உடன் ஒரு பாதையை வழங்குகிறது.

அரிசி. 4.26.

அடுத்த படி படத்தில் காட்டப்பட்டுள்ள முடிவை அளிக்கிறது. 4.27.

அரிசி. 4.27.

மேலும் குறிப்பது சாத்தியமில்லை. இங்கிருந்து நாம் அதிகபட்ச ஓட்ட மேட்ரிக்ஸைப் பெறுகிறோம் (படம் 4.28).

அரிசி. 4.28.

நெட்வொர்க்கில் அதிகபட்ச ஓட்டத்தைக் கண்டறிவதற்கான அல்காரிதத்தைப் பயன்படுத்துவதன் விளைவாக, முடிவுகள் படத்தில் காட்டப்பட்டுள்ளன. 4.29. வரைபடத்தின் வளைவுகளில் காட்டப்பட்டுள்ள அடைப்புக்குறிக்குள் உள்ள எண்களின் ஜோடி, வளைவின் அதிகபட்ச செயல்திறன் மற்றும் பிணையத்திற்கு வழங்கப்பட்ட பொருட்களின் பரிந்துரைக்கப்பட்ட அளவைக் குறிக்கிறது.

கணினி நெட்வொர்க்கின் சந்தாதாரர்களிடையே தகவல்களைப் பரிமாறிக் கொள்ளும்போது, ​​​​பல இயந்திர வளாகத்தில் இணையான கணக்கீடுகளின் போது, ​​ஒரு சிக்கலுக்கான தீர்வு பல செயலிகளிடையே விநியோகிக்கப்படும்போது, ​​​​கணினி நெட்வொர்க்கில் பகிரப்பட்ட நினைவகத்தைப் பயன்படுத்தும் போது, ​​ஒவ்வொரு செயலியும் பொதுவான நினைவகத்திற்கு வரையறுக்கப்பட்ட அணுகலைப் பெறும் போது தொகுதிகள், அதிகபட்ச தகவலை மாற்றுவதில் சிக்கல் எழுகிறது கொடுக்கப்பட்ட பிரிவுநேரம்.

போக்குவரத்து அமைப்பின் செயல்பாட்டின் போது, ​​நெட்வொர்க் முனைகளுக்கு இடையில் போக்குவரத்து அலகுகள் பரிமாற்றம் செய்யப்படும்போது, ​​ஒரு குறிப்பிட்ட காலப்பகுதியில் அதிகபட்ச போக்குவரத்து அலகுகளை மாற்றும் பணி எழுகிறது.

மின்சார நெட்வொர்க்குகளில் ஆற்றலை கடத்தும் போது அல்லது குழாய் அமைப்புகளில் திரவங்களை கடத்தும் போது, ​​ஒரு குறிப்பிட்ட காலப்பகுதியில் அதிகபட்ச அளவு ஆற்றல் அல்லது பொருளை விநியோகிப்பது மற்றும் கடத்துவதில் சிக்கல் எழுகிறது.

நெட்வொர்க்கின் ஒரு சிறப்பு அம்சம் ஒரு மூல உச்சி மற்றும் ஒரு மடு முனையின் இருப்பு, வரைபடத்தில் உள்ள அனைத்து வரி பிரிவுகளின் நோக்குநிலை மற்றும் சுழல்கள் மற்றும் பல வளைவுகள் இல்லாதது.

ஒரு பிணையத்தில் கணு x i இலிருந்து முனை x j க்கு மாற்றப்படும் தகவல், ஆற்றல் அல்லது பொருளின் அளவு அழைக்கப்படுகிறது ஓட்டம் மற்றும் j ij ஐக் குறிக்கிறது.

வில் (x i, x j) கடந்து செல்லும் மிகப்பெரிய ஓட்டம் என்று அழைக்கப்படுகிறது செயல்திறன் வளைவுகள் மற்றும் ij உடன் குறிக்கப்படுகின்றன.

ij உடன் 0 £ j ij £ என்பது வெளிப்படையானது.

மூல உச்சி x 0 இல், ஓட்ட மதிப்பு என்பது x 0 உச்சியில் இருந்து வெளிப்படும் அனைத்து வளைவுகளிலும் உள்ள ஓட்டங்களின் கூட்டுத்தொகையாகும், அதாவது. j=å i j 0i + .

சிங்க் வெர்டெக்ஸ் x k இல், ஓட்ட மதிப்பு என்பது x k இல் நுழையும் அனைத்து வளைவுகளிலும் உள்ள ஓட்டங்களின் கூட்டுத்தொகையாகும், அதாவது. j=å i j ik - .

எந்த இடைநிலை வெர்டெக்ஸ் x i க்கும், வெளிச்செல்லும் ஓட்டங்களின் கூட்டுத்தொகை உள்வரும் ஓட்டங்களின் கூட்டுத்தொகைக்கு சமம், அதாவது. å j j ij + =å k j ik - .

படத்தில். படம் 3.29, ஒரு மூல வெர்டெக்ஸ் x 0, ஒரு சிங்க் வெர்டெக்ஸ் x k மற்றும் இரண்டு இடைநிலை முனைகள் x i மற்றும் x j ஆகியவற்றைக் கொண்ட நிபந்தனை நெட்வொர்க்கைக் காட்டுகிறது. ஒவ்வொரு வளைவிலும், தொடர்புடைய வளைவின் ஓட்டம் மற்றும் திறன் அடைப்புக்குறிக்குள் குறிக்கப்படுகிறது. இந்த வழக்கில், பிணையத்திற்கு வழங்கப்பட்ட ஓட்டம் j=(j 0i +j 0j), பிணையத்திலிருந்து அகற்றப்பட்ட ஓட்டம் j=(j ik +j jk), உச்சி x i இலிருந்து x j வரையிலான ஓட்டத்திற்குச் சமம். j ijக்கு சமம். வெர்டெக்ஸ் x iக்கு j 0i =(j ij +j ik), உச்சிக்கு x j - j jk =(j 0j +j ij).

ஒரு வரைபடத்தின் செங்குத்துகளின் தொகுப்பானது இரண்டு இணையான துணைக்குழுக்களாகப் பிரிக்கப்பட்டால், அவற்றில் ஒன்று மூல உச்சியையும் மற்றொன்று மூழ்கும் உச்சியையும் கொண்டிருந்தால், இந்த இரண்டு தொகுப்புகளையும் இணைக்கும் வளைவுகளின் தொகுப்பு உருவாகிறது. வெட்டு A i , இதன் திறன் வளைவுகளின் திறனின் கூட்டுத்தொகைக்கு சமம். இதுபோன்ற பல வெட்டுக்கள் இருக்கலாம்.

படத்தில் பிணையத்திற்கான நான்கு பிரிவுகளை அட்டவணை காட்டுகிறது. 3.29

எடுத்துக்காட்டாக, வெட்டு A 1க்கு X'=(x 0) மற்றும் X\X'=(x i, x j, x k), A 2 - X'=(x 0, x i) மற்றும் X\X' =( x j, x k), A 3 - X'=(x 0, x i, x j) மற்றும் X\X'=(x k), A 4 - X'=(x 0, x j) மற்றும் X\X'=( x i, x k).

வெளிப்படையாக, அதிகபட்ச ஓட்டம் பிரிவின் குறைந்தபட்ச செயல்திறன் மூலம் வரையறுக்கப்பட்டுள்ளது, அதாவது.

j அதிகபட்சம் =நிமிடம்(С(A i))

எனவே, வளைவுகளின் கொடுக்கப்பட்ட திறன் கொண்ட நெட்வொர்க்கில் அதிகபட்ச ஓட்டம் வெட்டுகளின் திறனைக் கணக்கிட்டு அவற்றில் குறைந்தபட்சத்தைத் தேர்ந்தெடுப்பதன் மூலம் கண்டறியலாம். இருப்பினும், இந்த தீர்வுடன், வளைவுகள் வழியாக ஓட்டம் விநியோகம் தெரியவில்லை.

வளைவுகள் வழியாக ஓட்ட விநியோகத்தைத் தேட பல வழிமுறைகள் உருவாக்கப்பட்டுள்ளன. அவற்றில் ஒரு சிறப்பு இடம் ஃபோர்டு-ஃபுல்கர்சன் அல்காரிதம் மூலம் ஆக்கிரமிக்கப்பட்டுள்ளது, இதன் சாராம்சம் வரைபடத்தின் செங்குத்துகளைக் குறிக்கும்.

வரைபட உச்சியின் லேபிள் இந்த உச்சி வழியாக ஓட்டத்தை மாற்றுவதற்கான சாத்தியத்தை குறிக்கிறது மற்றும் இந்த மாற்றத்தின் மூலத்தைக் குறிக்கிறது. படத்தில். 3.30 அல்காரிதத்தின் சாரத்தை விளக்கும் நெட்வொர்க்கின் ஒரு பகுதியைக் காட்டுகிறது.

வளைவுடன் இருந்தால் (x s, x i) ஓட்டத்தை அதிகரிக்க முடியும் (j si< c si), то вершину х i следует пометить +s , что указывает на источник увеличения потока.

வளைவுடன் (x i, x j) இருந்தால், j ij ஓட்டத்தை அதிகரிக்க முடியும்< c ij , то вершину х j пометить +i . Это означает, что приращение потока Dj si пойдет по направлению дуги (х i , х j) от вершины х s .

ஆர்க் (x s, x i) நிறைவுற்றதாக இருந்தால், அதாவது. j si =c si, பிறகு +s குறியை x i என்ற உச்சியில் வைக்க முடியாது. எனவே, வெர்டெக்ஸ் x i குறிக்கப்படவில்லை என்றால், வெர்டெக்ஸ் x j ஐ +i என்று பெயரிட முடியாது.

வளைவில் (x t, x j) ஓட்டத்தில் அதிகரிப்பு சாத்தியம் என்றால், அதாவது. j tj< c tj , то вершину х j следует пометить +t , что указывает на источник увеличения потока.

வெர்டெக்ஸ் x j என்பது +i எனக் குறிக்கப்படவில்லை எனில், பிணையத் துண்டில் ஓட்டத்தை அதிகரிக்க, வளைவில் (x i, x j) ஓட்டத்தைக் குறைத்து, அந்தத் துண்டின் மற்ற வளைவுகளுடன் வடிகால் நோக்கிச் செல்ல வேண்டும். இதைக் குறிக்க, x i இன் உச்சியில் ஒரு லேபிள் - j வைக்கப்பட்டுள்ளது. இதன் பொருள், பகுதியில் (x i, x j) ஓட்டத்தில் பொதுவான அதிகரிப்புடன், அது Dj tj அளவு குறைக்கப்பட வேண்டும்.

ஆர்க் (x t, x j) நிறைவுற்றதாக இருந்தால், அதாவது. j tj =c tj, பிறகு +t லேபிளை x j என்ற உச்சியில் வைக்க முடியாது. எனவே, உச்சி x j குறிக்கப்படவில்லை என்றால், x i என்ற உச்சியை -j என்று பெயரிட முடியாது.

இரண்டு வளைவுகளும் (x s, x i) மற்றும் (x t, x j) நிறைவுற்றதாக இருந்தால், அதாவது ஓட்டம் Dj si மற்றும் Dj tj ஐ அதிகரிக்க இயலாது, பின்னர் x i மற்றும் x j என்ற முனைகளில் லேபிள்களை வைத்து அடுத்ததைக் குறிப்பதைத் தொடர முடியாது. பிணைய முனைகள் மூழ்கி உச்சிக்கு .

இந்த வழியில், ஓட்டத்தின் அதிகபட்ச மதிப்பு x s மற்றும் x t ஆகிய மூல முனைகளிலிருந்து வளைவுகளுடன் சேர்ந்து x i மற்றும் x j ஆகிய சிங்க் செங்குத்துகளுக்கு அடையப்படுகிறது.

Ford-Fulkerson அல்காரிதம்:

படி 1: வரைபடத்தின் அனைத்து முனைகளுக்கும் குறியீடுகள் 0,1,2,...k ஐ ஒதுக்கவும்; இதில் 0 என்பது வரைபடத்தின் மூல முனையின் குறியீடாகும், k என்பது வரைபடத்தின் சிங்க் உச்சியின் குறியீடாகும்;

படி 2: ஒதுக்கு ஆரம்ப உச்சிலேபிள் "0";

படி 3: குறிக்கப்பட்ட உச்சி x s இலிருந்து நிறைவுறாத வளைவுகள் செல்லும் அனைத்து குறிக்கப்படாத செங்குத்துகளும் "+s" குறியீட்டால் குறிக்கப்படுகின்றன, இது வளைவில் (х s, х i );

படி 4: வளைவுகள் (நிறைவுற்ற அல்லது நிறைவுறாத) குறிக்கப்பட்ட உச்சி x j க்கு “-j” குறியீட்டைக் கொண்டு செல்லும் அனைத்து குறிக்கப்படாத செங்குத்துகளையும் குறிக்கவும் (x i, x j)

படி 5: இந்த செயல்பாடுகளின் விளைவாக சின்க் வெர்டெக்ஸ் x k குறிக்கப்பட்டால், நெட்வொர்க்கின் ஆரம்ப மற்றும் இறுதி செங்குத்துகளுக்கு இடையில் ஒரு பாதை உள்ளது, அதன் அனைத்து முனைகளும் வேறுபட்டவை மற்றும் ஒரு அடையாளம் வரை, முந்தைய குறியீடுகளுடன் குறிக்கப்படும். செங்குத்துகள், ஒரு மாற்றத்தை உருவாக்குகிறது, அதனுடன் நீங்கள் ஓட்டத்தை அதிகரிக்கலாம் மற்றும் படி 6 க்கு செல்லலாம், இல்லையெனில் அது முடிந்துவிட்டது.

படி 6: படி 5 இல் உருவாக்கப்பட்ட பாதையில் ஓட்டத்தை ஒவ்வொன்றாக அதிகரித்து, படி 3 க்குச் செல்லவும்.

அல்காரிதத்தின் முடிவின் அடையாளம் ஒரு மூழ்கும் உச்சியைக் குறிக்கும் சாத்தியமற்றது.

உதாரணம்: படத்தில். 3.31 வரைபடம் கொடுக்கப்பட்டுள்ளது. நெட்வொர்க்கில் அதிகபட்ச ஓட்டம் மற்றும் அதன் விநியோகத்தின் மதிப்பைக் கண்டறியவும்.

ஒவ்வொரு ஆர்க்கிலும் (x i, x j) ஓட்ட மதிப்பு மற்றும் திறன் குறிக்கப்படுகிறது - (j ij, c ij).

அனைத்து கணக்கீடுகளும் இரண்டு அட்டவணைகளில் சுருக்கப்பட்டுள்ளன: அட்டவணை a)

அட்டவணை b)

அட்டவணையில் a) ஒவ்வொரு மறு செய்கை படியிலும், வரைபடத்தின் ஒவ்வொரு முனைக்கும் சாத்தியமான லேபிள்கள் குறிக்கப்படுகின்றன, மேலும் அட்டவணை b) வளைவுகளுடன் (x i, x j) ஓட்ட அதிகரிப்புகள் கொடுக்கப்பட்டுள்ளன. வரைபடத்தின் செறிவூட்டப்பட்ட வளைவுகள் தடிமனாக உயர்த்திக்காட்டப்படுகின்றன.

முதல் மறு செய்கையின் விளைவாக, பின்வரும் மாற்றங்கள் சாத்தியமாகும்: n 0k =((x k, x 1, x 0); (x k, x 2, x 0); (x k, x 2, x 3, x 0 (x k, x 2, x 3, x 1, x 0);

(x k, x 3, x 0); (x k, x 3, x 1, x 0)). n 0k =(x k, x 3, x 0) தேர்ந்தெடுக்கப்படும். Dj=1 இல் உள்ள ஓட்ட அதிகரிப்பு m=((x 0, x 3), (x 3, x k)) பாதையில் செல்கிறது.

இரண்டாவது கட்டத்தில், அதே மாற்றங்கள் சாத்தியமாகும். மாற்றம் n 0k = (x k, x 3, x 0) தேர்ந்தெடுக்கப்படட்டும். Dj=1 இல் உள்ள ஓட்ட அதிகரிப்பு m=((x 0, x 3), (x 3, x k)) பாதையில் செல்கிறது. இந்த வழக்கில், ஆர்க் (x 3, x k) நிறைவுற்றதாக மாறும், அதாவது j 3k =c 3k =2.

மூன்றாவது கட்டத்தில், மாற்றங்கள் சாத்தியமாகும்: n 0k = ((x k, x 1, x 0); (x k, x 2, x 0); (x k, x 2, x 3, x 0); (x k, x 2, x 3, x 1, x 0)). n 0k =(x k, x 2, x 3, x 1, x 0) தேர்ந்தெடுக்கப்படும். Dj=1 இல் உள்ள ஓட்ட அதிகரிப்பு m=((x 0 , x 1), (x 1 , x 3), (x 3 , x 2), (x 2 , x k)) பாதையில் செல்கிறது. இந்த வழக்கில், ஆர்க் (x 3, x 2) நிறைவுற்றதாக மாறும், அதாவது j 32 =c 32 =1.

நான்காவது கட்டத்தில், மாற்றங்கள் சாத்தியமாகும்: n 0k = ((x k, x 1, x 0); (x k, x 2, x 0)). n ok =(x k, x 1, x 0) தேர்ந்தெடுக்கப்பட வேண்டும். Dj=1 இல் உள்ள ஓட்ட அதிகரிப்பு m=((x 0 , x 1), (x 1 , x k)), பாதையில் செல்கிறது. இந்த வழக்கில், ஆர்க் (x 0, x 1) நிறைவுற்றதாக மாறும், அதாவது j 01 =c 01 =2.

ஐந்தாவது படியில், மாற்றங்கள் சாத்தியமாகும்: n 0k = ((x k, x 1, -x 3, x 0); (x k, x 2, x 0)). n ok =(x k, x 1, -x 3, x 0) ஐ தேர்ந்தெடுக்கலாம். Dj=1 இல் உள்ள ஓட்ட அதிகரிப்பு m=((x 0 , x 3), (x 3 , x 1), (x 1 , x k))), பாதையில் செல்கிறது. இந்த வழக்கில், ஆர்க் (x 0, x 3) நிறைவுற்றதாக மாறும், அதாவது j 03 =c 03 =3.

ஆறாவது படியில், வளைவுகள் (x 0, x 1) மற்றும் (x 0, x 3) நிறைவுற்றதால், ஒரே ஒரு மாற்றம் n 0k = (x k, x 2, x 0) மட்டுமே சாத்தியமாகும். Dj=1 மூலம் ஓட்ட அதிகரிப்பு m=((x 0 , x 2), (x 2 , x k)), பாதையில் செல்கிறது. இந்த வழக்கில், ஆர்க் (x 0, x 2) நிறைவுற்றதாக மாறும், அதாவது j 02 =c 02 =1.

ஏழாவது படியில், வளைவுகள் (x 0, x 1), (x 0, x 3) மற்றும் (x 0, x 2) நிறைவுற்றதால், x o இலிருந்து x k க்கு ஒரு மாற்றம் கூட சாத்தியமில்லை. x 1, x 2 மற்றும் x 3 ஆகிய முனைகளில் லேபிள்கள்.