0
Minimum maliyetli akış probleminin integral teoremi, "integral veriler" verildiğinde, her zaman minimum maliyet akışına karşılık gelen problem için ayrılmaz bir çözümün olduğunu belirtir. Entegral veri kavramı, çoğu makalede olduğu gibi bana biraz kafa karıştırıcı, öğreticiler taleplerin, arzların ve kapasitelerin ayrılmaz olduğunu söylüyor. Şimdi, bir kapasite kısıtı tipik olarak l_i alt kenarının i kapasitesine bağlı olduğu ve u_i üst sınır olduğuMin-Maliyet Akışı İntegralite Teoremi
l_i <= c_i <= u_i
olarak temsil edilir. İntegralite teoreminin tutulması için l_i and u_i'un tam sayı olması yeterli midir? Kuşkusuz bu, akışın her zaman tam olarak kendileri gibi olduğu anlamına gelmez, örneğin l_i = 0, u_i = 1, kenar i 0,5 akışa sahip olabilir.
teşekkür ederiz. Bütün ayrılmaz akışlara sahip bir çözümün var olduğunu mu söylüyor? Yoksa daha mı güçlü? Anlayışım, herhangi bir fraksiyonel akıştan daha kötü olmayacak bir integral akımın var olmasıydı. Ayrıca, bana bunun kanıtını gösterebilir misin? Belgelerin ve öğreticilerin, bunu kanıtlamadan veya b) orijinal kanıtı gerekçe göstermeden kabul etmeleri gariptir. – statBeginner
Daha güçlüdür. Maksimum akış, minimum kesim ile eşleşecek ve maksimum akış ve tüm ayrılmaz akışlarla bir çözüm var. Kanıt için http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07maxflow.pdf adresine bakın. – btilly