Тетрадка.бгR(3,3) , R(3,4) , R(3,5).

Всичко, което липсва във вашата тертадка, ще намерите в нашата Тетрадка.бг

Поръчай тема Услуги Абонаменти

Опсс.. няма качен документ за преглед :(

Изтегли сега

Изтегли сега с абонамент (10 кредита)

Купи веднага

Купи веднага 45 лв (еквивалент на 15 кредита)

admin

R(3,3) , R(3,4) , R(3,5).

Нека имаме пълен граф G и при всяко 2-оцветяване на ребрата на G не се получава едноцветен триъгълник. Тогава всеки връх на G има най-много 2 бели и най-много 2 черни ребра излизащи от него. Доказателство:Да допуснем, че A e връх в графа. А е свързан посредством бяло ребро с : B, C и D. Ако B и C са свързани също с бяло ребро, тогава заедно с А те образуват образуват триъгълникът АBC образуват триъгълникът (А,B,C), което е невъзможно.Следователно не са свързани никои два върха измежду B, C и D не са свързани с бяло ребро. Следователно B, C и D са свързани с черно. Тогава B, C и D образуват черен триъгълник. Противоречие с условието! което. Следователно допускането не е вярно. Теорема 1 е доказана. Теорема2.Нека имаме пълен граф с поне 5 върха и при всяко 2-оцветяване на ребрата не се получава едноцветен триъгълник. Тогава графът се състои точно от 5 върха. Доказателство:Съгласно Теорема 1, имаме, че графът има точно 5 върха, като от всеки връх излизат точно 2 бели и 2 черни ребра. Теорема 2 е доказана. Теорема3.При всяко 2-оцветяване на ребрата на пълен граф с поне 6 върха се получава или черен или бял триъгълник. Доказателство:Ако допуснем, че в графа ня

Референтен номер: 2774

Предназначен за: Студенти

Тип: Курсови работи

Категория: Математика

Брой страници: 10

Качен на: 01/10/2011

Институция: Софийски университет „Св. Климент Охридски”

Град: София