За теоретичния въпрос на изпита
Скоро ще съм готов с проверяването и ще сложа резултатите в муудъл.
Тъй като не мога да покажа писмените работи на студентите, докато трае корона-кризата, няколко бележки върху отговорите на теор. въпрос.
Теоретичният въпрос е за графи. Трябва да има формално коректни дефиниции на всички видове графи, за които става дума в изложението. Следната деф. не върши работа "Граф е наредена двойка (V,E), където V е м-вото от върховете, а E е м-вото от ребрата. Всяко ребро е между два върха". Трябва да се обясни каква е връзката между върховете и ребрата, защото не всяка наредена двойка от множества е граф. При графите не просто има две множества, а едното (ребрата) е дефинирано чрез другото (върховете), което на свой ред е първично (опорно м-во). "между" не е теоретико-множествено понятие и, докато не бъде дефинирано въз основа на вече известни понятия, е лексика без семантика. Житейски ние знаем какво е "между", но в теорията на м-вата до момента не сме го дефинирали, така че, формално, не знаем какво е.
Под "видове графи" аз имах предвид четирите комбинации от ор/неор, мулти/немулти. Те трябва да се дефинират прецизно, било както в учебника на професор Манев (където КОМ е най-общият вид, а останалите са частни случаи), било както е в моите лекционни записки. Класификации на графите от рода на "ориент, неор, мулти, не-мулти, свързани, двуделни, планарни ..." не са адекватни, защото някои от тези класове (свързани, двуделни, планарни) са подразделения на само един вид графи, а именно обикновените. За ориентираните графи терминът "свързан" не се използва изобщо, ориентираните биват силно или слабо свързани; същото е в сила за двуделните и планарните. Поставянето в един списък на класове (категории) графи от различни нивА показва концептуална обърканост.
Доколкото помня в момента, (почти) нямаше адекватно дефинирани "свързан граф" и "планарен граф".
И още нещо. НДУ за 2-оцветимост е отсъствието на нечетни цикли. Доста студенти са писали, че НДУ G да е оцветим е G да е двуделен. Това е слабо твърдение -- очевидно е, че 2-оцветим и двуделен са едно и също нещо при наличието на поне едно ребро.
-- ММ