Теория графов и комбинаторика

3. Вибратъ новый, ранее не расомотренный элемент Обозначить А СК+<) - множество вершин 6./{0<} , омеядах верине "IT . 4. Изменить множеотва /4f<) и ACi:+i) следующим образом: Л С » ^ + < ) = Д С К + 0 Ь ' / \ Ч К + < ) ; Л Е Ю = Д С К ) N А * С | : + 0 . i), Коли в множестве Дск) -имеетоя еще не раоомотреиная вершина, перейти к п . З , иначе к п.6. 6. Положить К = |;+< . Еоди И , перейти к п.З, иначе перейти к п . 7 . 1 7. Вычиолитъ оценку хроматического числе графа по фор^ла Хсв-)= X[ к \ ACK}i^^}. Другой простой метод раокраоки'замючаеюя в оледующем! вершины упорядочна аытоя в порядасе невозрастания их oreneitu .. Первая вершина окрашиваетоя в цвет I ; "затем в цвет I окраши- ваетоя каждая верп-ша, которая несмежна о другой, уже окрашен­ ной в этот ц в е т . Потом всзвращаемг i к- первой в описке неокра­ шенной вершина, окрашиваем ее в цвет 2 и , прооматривая описок неокрашенных вершин, окрашиваем в цвет 2 люйую вершину, неомеж- вую ,0 вершиной, ужк) окрашенной в цвет 2. Продолжрем втот про- Ц800 до тех пор , когда будут окрашены пое вершины. ГЛАВА. 13 . ЭЛЕЖНта КОШШЛТОРИКИ Комбитпторика - этс раздел дискретной математики, в ко­ тором изучаются операции отбора елементов из множеотв и их упорядочения о удовлетворением определенных условий, В овязи о этими операциши возникают три ооновных вопроса: а), с вов- ..эжнооти выполнения операций (вопроо оущеотвования); б) о чис­ ле способов Быполл^ния укЕ"?,энншс операций (вопрос перечиоления); в) разработке алгоритмов отыокания (пс: "роения) решений. В дальнейшем O ^ JHOBHOB внимание будет уделено задачам порачиоленпя, §13.1. Выбо йи. Основные правила комбинатотак!^. Выборкой наз1-1Бавтся результат выполнения операции отбс])а элементов нокоторого шожеотва. Пусть V - П,-множ.богво ,т, е. множество, оодаржа'чее И элементов. Дощ'отим, чтс производигоя . пооледовь^ ел'-ный отбор элемьигов. Возмсжны два схемы отбора; отбор о sosBj^aTONi, когда перед кааднм отбором элемента 1>аней выбранный елемонт во^зврацавхря в множество, и отбор без воэв- 7 7