Минимално покритие на върховете
Това ръководство е предназначено за студенти, изучаващи курса по дискретна математика и (или) теория на графите. С него ще усвоите темата "Минимално (претеглено) покритие на върховете". Направо от това ръководство можете да изчислите своя IPD, дори ако нямате MATLAB на вашия компютър. Ако имате MATLAB, отидете на тази страница: там имате възможност да се намесите в изчислителния скрипт (програма). Тук проблемът с претегленото минимално покритие на върховете се решава чрез редуцирането му до проблем с двоично линейно програмиране.
- n=V− размер на графа (брой върхове);
- m=E− мощност на графа (брой ребра);
- A− двоична (състояща се от нули и единици) матрица на инцидентност с размер на всеки от нейните елементи, акоi-тият връх е инцидентен наk-тото ребро; и в обратния случай; във всяка колона на такава матрица има точно две единици, а останалите са нули;
- v− двоичен колонен вектор с дължинаn; всеки от неговите елементи, акоi-ият връх е включен в минимално претегленото покритие на връх, и ако не е;
- d− колонен вектор от тегла на върхове с дължинаn;
- 1− колонен вектор от единици с необходима дължина;
- t− целева функция: общото тегло на върховете, включени в минимално претегленото покритие на върховете.
Тогава проблемът с минимално претеглено покритие на върха може да бъде формулиран като двоичен проблем с линейно програмиране:
Общото тегло на върховете, включени в минимално претегленото покритие на върховете (1), е сведено до минимум. Всяко ребро трябва да бъде инцидентно с поне един такъв връх (2) и всеки връх може или да бъде включен в покритието на върховете, или не (3).
За да работи правилно тази страница, вашият браузъртрябва да поддържаJava Scriptскриптове. Включете ги.
Въведете първоначалните данни в полетата за въвеждане по-долу. В първата област трябва (по-точно можете) да въведете координатите на върховете, за да начертаете графиката, и теглото на върховете. Координатите на върха са зададени от лявата страна. Те са зададени като матрица в първата колона - координати, във втората - Числата могат да бъдат зададени като цели числа, с десетична запетая или в експоненциална форма. Разделете числата с интервали. Общият брой редове в тази входна област определя размера на графикатаn− броят на върховете. Тези първоначални данни (координати на върха) не са задължителни: ако не са посочени, графиката ще бъде изчертана в правилната форма и броят на върховете ще се определя от максималния брой на върховете в следващата област за въвеждане. Теглата на върховете са посочени в дясната част на първата входна област като вектор с дължинаn. Ако теглата на върховете не са дадени, тогава се приема, че всички те са еднакви - единични и в този случай проблемът за максималното независимо множество от върхове (непретеглени) ще бъде решен.
Следващата област за въвеждане е задължителна. Той определя структурата на графиката. Всяко ребро в графиката свързва два върха. Номерата на тези върхове са дадени като матрица в тази област за въвеждане. Кой връх се счита за първи и кой за втори - няма значение. Тези колони трябва да съдържат естествени числа от 1 доnвключително. Разделете числата с интервали.