На головну

Оцінка числа неізоморфних графів з q ребрами

  1. D. Наступні дії і оцінка
  2. II. Обчислювальні іменники в англійській мові мають форму єдиного (Singular) і множинного (Plural) числа.
  3. Say these numbers in English. (Назвіть числа по-англійськи.)
  4. А) Оцінка рівня підготовленості нового працівника.
  5. Абсолютні числа розлучень і загальні коефіцієнти розлучуваності в США і СРСР,
  6. Адекватність, еквівалентному і оцінка перекладу
  7. Алгоритм операції зведення числа в ступінь по модулю.

Нехай ? (q) - число неізоморфних графів без ізольованих вершин з q ребрами.

Лемма 1.  , Де з - деяка константа.

Доведення: Так як за умовою існує q ребер, значить різних кінців в графі не більше 2q, значить, в нашому графі не більше 2q вершин. Ці вершини Занумеруем числами:

Початок графа можна вибрати 2q способами, кінець - теж 2q способами. Значить, все можливостей розмістити q ребер буде 2q * 2q = 4q2. Таким чином наша задача знаходження числа неізоморфних графів ? (q) зводиться до знаходження числа сполучень з повтореннями з 4q2 позицій по q. це число

=  , Де с = 5e.

Лема доведена.

 



Попередня   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   Наступна

Схеми з функціональних елементів | Визначення схем з функціональних елементів | Найпростіші методи синтезу | метод Шеннона | Спеціальне подання функцій | метод синтезу | Завдання для самостійної роботи | Елементи теорії графів | Способи завдання графа | Деякі співвідношення в графі |

© um.co.ua - учбові матеріали та реферати