Электронная библиотека Попечительского советамеханико-математического факультета Московского государственного университета
 Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум
 Авторизация Поиск по указателям
Berge C., Chvatal V. — Topics on Perfect Graphs (Annals of Discrete Mathematics, Volume 21)
 Обсудите книгу на научном форуме Нашли опечатку?Выделите ее мышкой и нажмите Ctrl+Enter Название: Topics on Perfect Graphs (Annals of Discrete Mathematics, Volume 21) Авторы: Berge C., Chvatal V. Аннотация: Many challenging problems in graph theory involve at least one of the following four invariants: (i) the stability number a (G) (also called the independence number), defined as the largest number of pairwise nonadjacent vertices in G; (ii) the clique covering number 8(G), defined as the least number of cliques which cover all the vertices of G; (iii) the clique number w(G), defined as the largest number of pairwise adjacent vertices in G; (iv) the chromatic number y(G) (sometimes denoted also by x(G)), defined as the least number of colors needed to color all the vertices in such a way that no two adjacent vertices have the same color. The inequality a (G) S O(G) holds trivially for all graphs G: if k cliques cover all the vertices then no more than k vertices can be pairwise nonadjacent. (A similar observation shows that w(G)S y(G). In fact, if G denotes the complement of G then o(G) = a (G) and y(G) = 8(C?).) Graphs which satisfy this inequality with the equality sign played an important role in Claude Shannon’s 1956 paper concerning the ‘zero error capacity of a noisy channel’. In this paper, Shannon remarked that the smallest graph G with a(G)< 8(G) is G, the cycle of length five. Язык: Рубрика: Разное/ Статус предметного указателя: Неизвестно ed2k: ed2k stats Год издания: 1984 Количество страниц: 384 Добавлена в каталог: 10.02.2018 Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Реклама
 © Электронная библиотека попечительского совета мехмата МГУ, 2004-2021 | | О проекте