Основы теории графов 01: напоминание определений, теорема Форда—Фалкерсона

  • Published on
    07-Jul-2015

  • View
    135

  • Download
    3

Embed Size (px)

DESCRIPTION

, , .. () , . [ , 2013 .]

Transcript

  • 1. 2013 www.dainiak.com

2. ? , BobAliceJohn 3. ? , , , ,V = , , E = , , , , , , (), 4. , , , , ( ) , , . , 5. , , / , , , 6. ( , ) (, ). . , 1,2,3,4 , 1,2 , 1,3 , 1,4 , 2,3 , 2,4 , 3,4 - : 7. , : 1,2,3,4 , 1,2 , 1,3 , 1,4 , 2,3 , 2,4 , 3,4, , , , , , , , , , , , , , , : , 8. , , , , : : , = 9. , , , , , : = 1,2,3 , = 1,2 , 1,3 = , , , = , , , : 1 , 2 , 3 10. , ( ), (.. ), : 11. , , , , 12. = , = , . , , = , :, , ( ) 13. / = , . , , , , + , 14. . , , = A , ( ) deg 15. : , + , = + + 16. 0 1 2 17. , : = max : = min : =1 18. : = 2 19. ( ), :1 12 232234 45 561234561234 5 20. , (.. ) / 21. , 22. , , 23. , , . : , . :diam = max, , = , = 3 24. , (?)4 5 25. , 26. 27. , , ( )3,3 28. , 0 ( ), : : , 2523 1132856 29. , , , : 0 ( = 0 ) = , : , , : = max 30. :2402 11223552523 1132856 31. , :max , :max 32. : , 2402 11223552523 1132856 33. : = , , :2523 1132856 34. , , max min, min 35. . max = min, , . 36. : 37. , :2523 113285611 1 38. . :2523 11328561522 113285611 111 39. . . 0 , 0 , = 0 0 , = 0 40. - . , :1522 113285611111111 41. - . , :11111111 1 22 11111 42. , .2402 11223552523 11328562121 11125512532 43. , . , , , . , .2121 11125512532 44. . , .5 552222 2223? 45. . , .5 552222 22232 46. , ( ). ,, , . , , .