Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 46
Текст из файла (страница 46)
Привести пример 3-сзюного графа. 3.19. Показать, что с точностью да иаоморфкзма имеется ровно 4 графа (олин иа которых полный) без параллешвых ребер и петель на трех вершинах, 11— нз четырех вершинах. Определить количество графов нв пяти вершинах. 3.19. Реберкым лдром грагуа С называется попграф, представляющий собой объединение множества ребер у, таких, что ребра каждого множества попарно несмевны н [у.[ = ие(С).
1!ризести примеры графов, не имеющих реберного ядра. 3.30. Найти необходимые условна, прн которых число ребер в графе разно произведению ооро. 3.31. Доказать или опровергнуть, что для юобаго свяаного графа Бе < еа. З.ЗЗ. Вгзчнслить х~(К м) и ег(Кеса). 3.33. Допевать, чта цикл нечетной длины невложим а я-мерный гиперкуб.
3 34. Показать, что диаметр я-куба а(С„) не может быть больше я. 3.35. Пусть граф С состоит нз Ь вершинно непересекающихся простых цепей мевлу двумя вершинами а, Ь Е С; длины всех цепей рааличны. Прн каком условии агат граф кубируем? 3.36. Определить платность графа, являющегося суммой ребра и цикла длины 5. 3.37. Для грифа, определенного в предыдущем упражнении, вычислить число внутренней устойчивости. З.ЙВ. Для графа, являющегося враиаведением ребра н цикла длины 4, опре'делить число внешней устойчивости. 3.39. Найти минимальную раскраску ребер графа Петерсена.
3.30. Обладзег лн свойством реберности граф, являющийся суммой изолгь равенной вершины и цикла длины 5? 3.31. Вычислить хроматическое число графа Петерсена. В 3.12. Номментйрнн Теория графов как раздел дискретной математики имеет многочисленные предметные ннтерпрегвпин. Оиа успешно применяется в задачах управления производством и при проектировании сетей ЭВМ, при рааработке современных электронных модулей и ври проектировании физических систем с сосредоточенными параметрами (акустических, механических, электрических), при решенви проблем генетики и проблем автоматизации проектирования (САПР). Теория графов является основой математического абеспеченйя современных систем абвботкн пиформапии.
Эта теория находит применение в ядерны~ исследованиях аграымная техника Фейгмаиа) и в финансовой области. Более подробные сведения о теоретико-графовых моделях и нх приложениях гбожна найти в [19, 26, 31, 44, 45[. 14.1. Формальные грамматики 259 В ивчвае было слово. иоанн, 1,1 Глава 4 ТЕОРИЯ ФОРМАЛЬНЫХ ГРАММАТИК И АВТОМАТОВ $4.1.
Формальные грамматики Рассмохрим систему подстановок, задаваемую алфавихом М = = (т;/ з = 1, ..., р) и баэиеными подстановками ст; -+Д, (4.1) где сз;,,й; — формулы (слова), быть можех, пусхые в алфавите М. Каждую подстановку ся -+ 111 будем понимахь как правило вывода. Часто сисхему подстановок называюх налусиетемами Тйэ в честь норвежского математика Акселя Туэ. Используя эти полусисхемы, Н. Хомский (1955 г.) сформировал и развил аппарат формальных грамматик. Определим поняхие формальной грамматики, кохорую в дальнейшем будем называть просто грамматикой.
Рассмотрим конечный алфавих М = (тз, тз, ..., т„), элементы которого будем называть символами (буквами), а конечные последовахельности символов — словами. Обозначим все множество слов, на длину которых не наложены никакие ограничения, Яо. Будем говорнхь, чхо Я С Яо — язык в алфавите М. Пусть С вЂ” некоторая совокупность правил, с помощью которых в М порождаются все слова, принадлежащие языку Я, и только они. Совокупносхь правил С будем называхь гралзматикай языка Я.
Два языка будем называть эквивалентными, если множества слов, из которых они сосхоят, совпадают. Две граммахики, Сз и Сз, над Яназываюхся эквивалентными, если языки, ими порождаемые, эквиваленхны. Условимся говорить, что С вЂ” гралзматика е конечным числом состояний, если правила порождения слов из алфавита М = = (тз, таз, .. ч т„) задаются следующим образом. Существует конечное множество состояний (Яо, 51, ..
ч 5,) и каждому Яз (э = 1, 2,..., г) сопоставляется набор пар вида (тч Я ), где з б (1, 2, ... ...,и), а б 10, 1, ..., г). Состоянию Яо соносхавляются пары вида (то, Яь), где й б 11, 2, ..., г). Символ нзо — специальный знак пробела между словами. Конструирование слов происходит следующим образом: из сосхояния Яо переходим в любое сосхояние Яч. Из пар, сопоставленных выбранному Ят, берут любую пару (т;, 51). Этот выбор определяех следующее состояние 51 и первый символ слова тя;. Далее про- М (ти тз, тз1 цесс построения слова нроисходих анало- т гично. Слово заканчивается при переходе к заключительному состоянию, как правите тз тз ло, Яо Язык, порождаемый грамматикой и тз 'конечным числом состояний, называехся 'аз языкам с конечным числом состояний. Структуру хаких языков удобно изображахь Р„с, 4л в виде графа, вершины которого сопосхавлены состояниям 5;, а дуги — парам (та;, Ят).
На рис. 4.1 приведен пример такого графа. С помощью грамматики, задаваемой этим графом„порождается язык, кохорый состоит из следующего множества слов: 1тз тз, тзтзтатз, тз тзтзтатз тз тз(тз) тзтзтз, тзтз(тз)тзтз). Порождение цепочек символов можно рассматривать как результат работы некоторого гипохетического устройства (рис.
4.2). Вдоль бесконечной (в обе или в одну сторону) ленты, разделенной на клетки, перемещается управляющая головка (УГ). Заданы Рис. 4.2 внешний алфавит М = 1то, тз, тз, ..., т„), символы которого называются буквами, внутренний алфавих 5 = (Яо, 51, ..., 5„), символы кохорого называются еаетпаяниями, и алфавит перемещений Р = 1П, Л, Н). Все клетки ленхы заполнены символами ,из М, по одному символу в каждой клетке. Символ та играет роль пустого символа (если в некоторой клехке стоих нзо, то в клехке .:ничего не записано). Предполагается, что вся бесконечная лента всегда заполнена символами пзо, за исключением тех клеток, где записаны какие-либо другие символы из М.
Управляющая головка может находиться в хех или иных состояниях, харакхеризуемых символами из 5. Сосхояние Яо особое. Ксли УГ находихся в состоянии Яо, то машина не производих ни'какой работы (выключена). Предполагается, что в конце работы машина всегда переходит в состояние Яо. В процессе работы мацзины УГ можех перемещаться в дискретные такхы времени вдоль ~аенхы. Перемещение происходих либо на одну клетку вправо (П), либо на одну клетку влево (Л). Перемещение УГ в данный такт работы может отсутствовать (Н). 260 Гл.4. Теория формальных грамматик и автоматов ~ 4.1.
Формальные грамматики 261 В каждый такт работы УГ совершает следующие действия: 1) считывает символ т;, находящийся в клетке ленты, которую в этом такте видит УГ; 2) в соответствии со считанным символом те и своим состоянием Я записывает символ ть в эту клетку; 3) движется (не движется) вдоль ленты; 4) переходит в следующее состояние Яр. Всю работу машины можно задать с помощью функциональной таблицы Т, в клетках которой стоят тройки вида ть, Яр, дь где 4 ŠР— символ, определяющий перемещение. Таким образом, функциональная таблица определяет отображение М х Я в М х Ях хР. Содержательный смысл отображения (тп;, Я ) -ь (ть, Яр, д~) состоит в том, что, находясь в состоянии Я и счйтывая из клетки символ т;, УГ записывает в данную клетку ленты символ ть, переходит в состояние Яр и производит движение, определяемое символом еб.
Условимся, что функциональная таблица всегда устроена так, что имеет место отображение (т;, Яо) -+ (т;, Яо, Н). Это означает, что в выключенном состоянии машина не работает. До начала функционирования машины (если это необходимо) надо заполнить некоторые клетки ленты символами, отличными от то, перевести УГ в состояние, отличное от Яо, и задать исходное положение УГ относительно ленты. После этого машина будет функционировать в соответствии с таблицей Т. Функционирование машины можно задать с помощью графа, вершины которого взаимно однозначно соответствуют состояниям этого устройства, дуги — переходам из одного состояния в другое, при эхом каж- даЯ лУга (Я;, Яр) взвешена паРой (тб тьд1). СледУЯ ХомскомУ, часто состояние называют нетерминальным (вспомогательным) символом, символ т; С М вЂ” терминальным.
Описанное гипотетическое устройство называется машиной Тьюринга. Тезис Поста. Производимая полусистема Туэ может быть представлена как машина Тьюринга, и наоборот. В гл. 1 было рассмотрено интуитивное определение понятия алгоритма. Используя машину Тьюринга, уточним это понятие. Тезис Тьюринга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
