شبکه شاره

برای تحلیل شبکه‌های حمل و نقل که وسیله حمل کالاها از مراکز تولید به بازار هستند یا شبکه‌های مخابراتی که داده‌ها را منتقل می‌کنند یا شبکه‌های رایانه‌ای یا شبکه خطوط انتقال گاز در شهرها را توسط گراف‌های سودار مورد تحلیل قرار می‌دهیم. مشاهده می‌شود که در این‌گونه شبکه‌ها، گراف معادل نیازمند ساختار یا مؤلفه‌هایی اضافی است؛ مثلاً به‌طور خاص بایستی هر یال سودار دارای عدد مثبت یا صفری به عنوان میزان ظرفیت آن باشد که این عدد نشان دهنده ظرفیت حمل داده در این خط است. تحلیل شبکه‌های شاره دارای دامنه وسیعی از این کاربردهاست.

پیشینه تاریخی

در ۱۹۳۰ بیان مسئله راه‌آهن شوروی موجب تحریک آمریکایی‌ها برای حل این مسئله شد. در ابتدای سال ۱۹۵۵این مسئله توسط تی. ای. هریس[۱] به صورت دیگری بیان شد: شبکهٔ راه‌آهنی را در نظر بگیرید که دو شهر را از طریق تعدادی شهرهای میانی به هم وصل کرده‌است. در این شبکه، هر مسیر دارای عددی است که نشان دهنده ظرفیت انتقال آن مسیر می‌باشد. وضعیت پایداری را در نظر بگیرید؛ بیشترین شاره‌ای که می‌تواند از هر شهر دلخواه خارج شود و به شهر مشخص دیگری وارد شود، چقدر است؟ فورد و فالکرسون بیان کردند که هریس در سال ۹۵ یک مدل ساده از جریان ترافیک در این مسئله ارائه کرد.

تعریف

گراف سودار (G=(V,E را یک شبکه شاره می‌نامیم اگر:

  • اولاً هر یال v,u)€ E) دارای یک میزان ظرفیت غیر منفی یعنیc(u,v)≥۰ است. برای زوج‌های (u,v) که در E وجود ندارند ظرفیت آن‌ها را صفر فرض می‌کنیم. همچنین چنانچه E دارای یالی مانند (u,v) باشد، یال (v,u) در جهت مخالف آن در گراف موجود نباشد.
  • ثانیاً دو راس مجزای s با نام منبع و t با نام چاهک در این گراف وجود دارد که s فقط مبدأ چند یال و t فقط مقصد چند یال است و هر راس دیگر گراف در مسیری از s به t قرار می‌گیرد.

شرط شارش

یک شبکه جریان به همراه جریان و ظرفیت.

اگر (G=(V,E یک شبکه شاره با منبع s و چاهک t باشد، یک شارش در G f:V×V تابع است که سه شرط زیر را ارضا می‌کند:

  • ۱»شرط محدودیت ظرفیت: برای هر u,v€ V بایستی (f(u,v)≤c(u,v باشد.
  • ۲»شرط تقارن شارش: برای هر u,v€ V بایستی (f(u,v)= - f(v,u باشد.
  • ۳»شرط بقای شارش: برای هر {u€V – {s،t بایستی v∈V) f(u,v) =۰)_∑ باشد.

اندازه شارش

مقدار شارش در هر یال می‌تواند عدد حقیقی منفی یا مثبت یا صفر باشد. اندازه شارش f را مساوی مقدار شارش خروجی از منبع تعریف می‌کنیم؛ یعنی: (f| = ∑_(v∈V)f(s,v|

کاربرد

یک مسئله مهم در مورد شبکه‌های شاره، یافتن [شارش بیشینه] است. از دیدگاه کاربردی تابع شارش بیشینه نشان دهنده بهترین روش استفاده از شبکه شاره در انتقال کالا یا داده از منبع به چاهک است. الگوریتم فورد-فالکرسون شارش بیشینه در یک شبکه شاره را به دست می‌دهد.

منابع برای مطالعه بیشتر

  • مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش
  • ریاضیات گسسته و الگوریتم ها-پدیدآورنده:علی بهفروز، محمد ایزدی-ناشر:آییژ
  1. T.E. Harris

Read other articles:

Konsonan sengau dwibibir langit-langit belakangŋ͡mNomor IPA119 (114)Pengkodean karakterEntitas (desimal)ŋ​͡​mUnikode (heks)U+014B U+0361 U+006DX-SAMPANmKirshenbaumNmSampel suaranoicon sumber · bantuan Konsonan sengau dwibibir langit-langit belakang merupakan konsonan yang dapat ditemui dalam beberapa bahasa. Dalam transkripsi IPA, suara ini dilambangkan dengan ⟨ŋ͡m⟩ yang merupakan gabungan konsonan sengau l...

 

Skydance MediaJenisSwastaIndustriPerfilmanTelevisiDidirikan2006; 17 tahun lalu (2006)PendiriDavid EllisonKantorpusatSanta Monica, California, Amerika SerikatWilayah operasiGlobalTokohkunciDavid Ellison, CEODana Goldberg, CCOJesse Sisgold, Presiden dan COOLarry Wasserman, CFOAnne Globe, CMOMarcy Ross, Presiden (TV)Don Granger, Presiden (Film)Bill Damaschke, Presiden (Animasi)PemilikDavid Ellison (controlling)Tencent (5%-10%)[1]DivisiSkydance (Film)Skydance AnimationSkydance Televi...

 

Meritxell Alseda Aizcorbe Plaats uw zelfgemaakte foto hier Persoonlijke informatie Volledige naam Meritxell Alseda Aizcorbe Geboortedatum 13 augustus 1982 Nationaliteit Spaanse Lengte 178cm Sportieve informatie Discipline Volleybal Beachvolleybal Positie Spelverdeler Seizoen Club 2000-20012001-20022002-20072007-20112011-20122012-2013 Hotel Cantur Las Palmas CV Playas de Benidorm Patricia Volei Ciutadella Haro Rioja Vóley Asterix Kieldrecht Haro Rioja Vóley Portaal    Sport Meritxe...

Kedutaan besar beralih ke halaman ini. Untuk kantor atau organisasi yang menjalankan fungsi kedutaan besar secara de facto, lihat Kedutaan besar de facto. Kedutaan Besar Republik Indonesia di Canberra, Australia Kedutaan Besar Spanyol untuk Takhta Suci dan Ordo Militer Berdaulat Malta di Roma Kedutaan Besar Norwegia untuk Amerika Serikat di Washington, D.C. Beberapa kedutaan besar dalam satu lokasi: Kedutaan besar Denmark, Finlandia, Islandia, Norwegia, dan Swedia di sebuah kompleks gedung di...

 

أشلند   الإحداثيات 39°53′17″N 90°00′32″W / 39.8881°N 90.0089°W / 39.8881; -90.0089  تقسيم إداري  البلد الولايات المتحدة[1]  التقسيم الأعلى مقاطعة كاس، إلينوي  خصائص جغرافية  المساحة 0.73 ميل مربع  ارتفاع 623 قدم  عدد السكان  عدد السكان 1218 (1 أبريل 2020)[2]1333 (1 أب

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) هذه قائمة الكواكب الصغيرة المرقمة في النظام الشمسي من 13001 - إلي -14000   قريبة من الأرض     الح...

穆罕默德·穆萨维出生1987年8月22日  (36歲)迪茲富勒 職業排球運動員、沙灘排球運動員  赛义德·穆罕默德·穆萨维·埃拉吉(波斯語:سید محمد موسوی عراقی‎,1987年8月22日—),伊朗男子排球运动员,2010年亚洲运动会男子排球银牌得主、2014年亚洲运动会男子排球金牌得主、2018年亚洲运动会男子排球金牌得主、2022年亚洲运动会男子排球金牌得主。[1...

 

Peta yang menunjukkan letak Tulunan Tulunan adalah munisipalitas di provinsi Cotabato, Filipina. Pada tahun 2009, munisipalitas ini memiliki populasi sebesar 47.159 jiwa atau 9.432 rumah tangga. Pembagian wilayah Secara politis Tulunan terbagi atas 29 barangay, yaitu: Bagumbayan Banayal Batang Bituan Bual Daig Damawato Dungos Kanibong La Esperanza Lampagang Bunawan Magbok Maybula Minapan New Caridad New Culasi New Panay Paraiso Poblacion Popoyon Sibsib Tambac Tuburan F. Cajelo Bacong Galidan ...

 

Джерело № 1Країна  УкраїнаРозташування Україна,Закарпатська область, Тячівський районПлоща 0,5Засновано 1984Оператор Русько-Мокрянська сільська радаПосилання Джерело № 1 — гідрологічна пам'ятка природи місцевого значення. Об'єкт розташований на території Тячівсько

Colombian public television channel Official logo Telecafé is a Colombian regional public television channel, launched on October 17, 1992.[1] The channel covers the departments of Caldas, Quindío and Risaralda. It broadcasts from studios in the cities of Manizales, Armenia and Pereira.[1][2] Its programming is general. References ^ a b García, Ana Patricia (2012). Televisión en Colombia: surgimiento de los canales regionales (PDF). Revista Luciérnaga (in Spanish)...

 

Guidlhall in Bath, headquarters of Bath and North East Somerset Council Bath and North East Somerset Council is the local authority for the unitary authority of Bath and North East Somerset, England. The council is elected every four years by the first past the post system of election and currently consists of 59 councillors, representing 33 electoral wards. The Liberal Democrats are currently the largest party on the council, having gained majority control in the 2019 local elections. The co...

 

Branch of cryptography Neural cryptography is a branch of cryptography dedicated to analyzing the application of stochastic algorithms, especially artificial neural network algorithms, for use in encryption and cryptanalysis. Definition Artificial neural networks are well known for their ability to selectively explore the solution space of a given problem. This feature finds a natural niche of application in the field of cryptanalysis. At the same time, neural networks offer a new approach to...

Indian TV series or programme IdhayamGenreSoap operaWritten byR. Selvaraj (screenwriter) dialogues Thirugnanasundaram I. AshokanScreenplay byDevi Bala R.SelvarajStory byDevi BalaDirected byB.NithyanandamCreative directorT.G.ThiyagarajanStarringNithya Das Seetha Sanjeev Nalini Shreekumar Devadarshini Neelima RaniTheme music composerSrinivasOpening themeIdhayam Idhayam(Vocals)Shweta MohanAjeeshYugabharathi (Lyrics)ComposerKiranCountry of originIndiaOriginal languageTamilNo. of seasons1No. ...

 

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Tristar film – news · newspapers · books · scholar · JSTOR (June 2019) (Learn how and when to remove this template message) 1996 Hong Kong filmTristarFilm posterChinese nameTraditional Chinese大三元Simplified Chinese大三元TranscriptionsStandard ...

 

Comics character created by Carl Critchlow Comics character Thrud the BarbarianThrud in a Frank Frazetta-inspired pose in Critchlow's painted style[1] on the cover of issue 1 of the Thrud the Barbarian full-length comic.Publication informationPublisherGames Workshop (1983–1988), Carl Critchlow (2002–2007)First appearanceArken Sword (1981)Created byCarl CritchlowIn-story informationSpeciesBarbarianTeam affiliationsNoneAbilitiesStrength of a rhinocerosSpeed of a jungle catIntelligen...

DDT

DDT Nama Nama IUPAC 1,1,1-Trichloro-2,2-bis(4-chlorophenyl)ethane Penanda Nomor CAS 50-29-3 Y Model 3D (JSmol) Gambar interaktif 3DMet {{{3DMet}}} ChEBI CHEBI:16130 Y ChEMBL ChEMBL416898 N ChemSpider 2928 Y Nomor EC KEGG D07367 Y PubChem CID 3036 Nomor RTECS {{{value}}} UNII CIW5S16655 Y CompTox Dashboard (EPA) DTXSID4020375 InChI InChI=1S/C14H9Cl5/c15-11-5-1-9(2-6-11)13(14(17,18)19)10-3-7-12(16)8-4-10/h1-8,13H YKey: YVGGHNCTFXOJCH-UHFFFAOYSA-N YIn...

 

Rieger Orgelbau GmbH Logo Rechtsform Gesellschaft mit beschränkter Haftung Gründung 1845 Sitz Schwarzach (Vorarlberg) Branche Musikinstrument Website rieger-orgelbau.com Produktions- und Verwaltungsgebäude in Schwarzach Moderne Ausgabe des Logos Rieger Orgelbau ist eine österreichische Orgelbaufirma, die auf das 1845 in Jägerndorf (Österreichisch-Schlesien) von Franz Rieger gegründete Unternehmen zurückgeht. Seit der Vertreibung der Inhaber aus der Tschechoslowakei 1946 hat sie ihren ...

 

Spitzname(n) Young Warriors(Junge Krieger) Verband Namibia Football Association Cheftrainer James Britz FIFA-Code NAM Statistik Erstes LänderspielLesotho – Namibia 3:01990 Höchster SiegSeychellen – Namibia 1:64. Dezember 2007 Höchste NiederlageSüdafrika – Namibia 9:06. Dezember 2009 Erfolge bei Turnieren Parameter konföderation fehlt oder ist fehlerhaft Endrundenteilnahmen 1 (Erste: 2021) Beste Ergebnisse Vorrunde 2021 COSAFA U-20-Meisterschaft Endrundenteilnahmen 6 Beste Ergebniss...

1954 home designed by Frank Lloyd Wright, Racine, WI, US The Keland House, also known as the Keland-Johnson House, located in Racine, Wisconsin, in the United States, was designed by Frank Lloyd Wright in 1954,[1] almost 50 years after he designed the Thomas P. Hardy House in Racine. It is currently known as the Boyd Home. Background The residence is on a bluff, cantilevered over the Root River and overlooking Colonial Park. The only furniture that Wright designed for the home were bu...

 

Abandoned railway line in Norway Holmestrand–Hvittingfoss LineAluminum train in Holmestrand in 1923OverviewNative nameHolmestrand–HvittingfossbanenStatusAbandonedOwnerVestfold PrivatbanerTerminiHolmestrandHvittingfossServiceTypeRailwaySystemNorwegian railwaysOperator(s)Vestfold PrivatbanerHistoryOpened30 September 1902Closed1 June 1938TechnicalLine length29.80 km (18.52 mi)Number of tracksSingleCharacterFreight of pulpTrack gauge1,067 mm (3 ft 6 in)Electrific...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!