Логикалық есептерді граф арқылы шешу

Шешуі. Үш жиын алып, олардан үштен нүкте қарастырамыз. Оларды адамдар аттарының бас әріптері пәндер мен қалалардың аттарының бірінші әріптерімен белгілейміз. Әт түрлі жиыннан алынған нүктелер бір ғана адамның қасиеттерін бейнелей алса, онда ол нүктелердің тұтас (үзіліссіз) сызықтармен қосамыз, егер олар әр түрлі адамның белгілерін білдірсе, үзік сызықтармен (штрихтармен) қосамыз. Есептің бірілгендері 1 – суретте кескіндеп көрсетілген.

Граф есеп шартында көрсетілген жиын элементі және олардың арасындағы байланыс ретінде болады. Бұл есеп граф тілінде төбелері үш жиында жатқан, қабырғалары тұтас сызықтармен қосылған үш үшбұрышты салуға келтіріледі. ХD – сәйкес келмейді, Х пен D-ны үзік сызықпен қосамыз, ол АХ сәйкес келеді (Астанада тұратын мұғалім химиядан сабақ береді), Д мен А сәйкес келмейді – ДА, сондықтан Д мен Х сәйкес келмейді (2 – сурет). Граф арқылы осыесепке ұқсас есепті шешекенде мынадай ережелерді пайдаланамыз: 1) үш төбесі үш жиында жатқан үшбұраштың бір қабырғасы тұтас сызықпен, екіншісі үзік сызықпен сызылса онда үшінші қабырғасы үзік сызықпен сызылады; 2) жиынның бір нүктесінен 2 – жиындағы 2 нүктеге үзік сызық жүргізілсе, онда үшіншісіне тұтас сызық жүргізіледі; 3) егер төбелері әр түрлі жиында жатқан үшбұрыштың екі қабырғасы тұтас сызықпен сызылса, онда үшіншісі де тұтас сызықпен қосылады.

Ережеге сүйеніп Ф мен Д-ны тұтас сызықпен қосамыз (ФД). МД – үзік болады, себебі ДФМ үшбұрашында ДФ – тұтас, ФМ – үзік. ДК тұтас сызықпен қосылады, себебі ДМ, ДА – үзік сызықтар. ФК – тұтас сызық. Олай болса, ДФК – үшбұрашаның қабырғалары тұтас сызық болады. МС, ИА, ХИ, БМ, БС тұтас сызықтарын жүргіземіз. Сонда ДФК, АХИ және СМБ – үшбұрышының төбелеріндегі элементтер сәйкес келіп, есептің сұрағына жауап береді, яғни Сәтжан – биолог, Маңғыстауда тұрады: Игілік – Астаналық, химиядан сабақ береді; ДосжанКөкшетауда тұрады, физикадан сабақ береді.

2-есеп: Дүйсенбі күнгі сабақ кестесін құру кезінде үш мұғалім мынадай өтініш айтты: 1) математика бірінші не екінші, 2) тарих бірінші не үшінші, 3) әдебиет екінші не үшінші болсын. Қанша тәсілмен мұғалімдердің өтінішін орындауға болады?