Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Числові характеристики графа

 

Означення 2.1.10. Напівстепенем виходу вершини називають кількість вихідних з неї дуг.

Означення 2.1.11. Напівстепенем входу вершини називають кількість вхідних до неї дуг.

Означення 2.1.12. Степенем (валентністю) вершини називають суму її вхідних та вихідних дуг.

.

Вершину, степінь якої дорівнює 0, називають ізольованою. Вершину, степінь якої дорівнює 1, називають висячою.

Граф, всі вершини якого мають однаковий степінь, називають регулярним або однорідним.

Лема про рукостискання. Сума степенів всіх вершин графа є парним числом.

Наслідок. У довільному графі кількість вершин непарного степеня – число парне.

Теорема 2.1.1. Максимальна кількість ребер у плоскому графі обчислюється за формулою .

Теорема 2.1.2. Кількість ребер у повному графі обчислюється за формулою .

Теорема 2.1.3. Кількість ребер у регулярному плоскому графі обчислюється за формулою , де – показник регулярності графа (степінь всіх вершин).

Теорема 2.1.4. Найбільша кількість ребер у графі, який не має трикутних граней, обчислюється за формулою .

Теорема 2.1.5. Максимальна кількість ребер у повному дводольному графі обчислюється за формулою , де .

Теорема 2.1.6. Стала залежність між кількістю вершин, ребер і граней плоского графа визначається за формулою Ейлера: , де – кількість вершин, – кількість ребер, а – кількість граней графа.

 

 


Читайте також:

  1. V. Поняття та ознаки (характеристики) злочинності
  2. Акустичні характеристики порід
  3. БОЙОВІ ТА ТЕХНІЧНІ ХАРАКТЕРИСТИКИ СТРІЛЕЦЬКОЇ ЗБРОЇ
  4. Большему насыщению магнитной цепи синхронного генератора соответствует точка характеристики холостого хода
  5. Будова осцилографа
  6. Будова, принцип роботи та характеристики МДН – транзисторів
  7. Будова, принцип роботи та характеристики тиристорів
  8. Будова, характеристики і параметри біполярного транзистора
  9. В качестве характеристики случайного рассеивания экспериментальных данных результата измерений принимают
  10. Варіаційні ряди та їх характеристики
  11. Векторні характеристикимеханічного руху– переміщення, шлях, швидкіст та прискорення
  12. Виберіть відповідні характеристики рівнів пізнання істини




Переглядів: 1276

<== попередня сторінка | наступна сторінка ==>
Ізоморфізм графів. Підграф. Суграф. Частковий граф | Маршрути незамкнені (ланцюги, шляхи) і замкнені (цикли, контури). Повнота. Зв’язність. Сильна зв’язність

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.007 сек.