Тестовый сборник вопросов

Материал из OSTIS_GT
Перейти к: навигация, поиск

Информационно поисковые вопросы

Что такое граф?

Ответ на вопрос на естественном языке:
Граф - это ...

Знания необходимые в базе знаний для ответа на вопрос:
Запись определения графа на естественном языке



Как классифицируются графы по различным признакам?



В чем отличие между планарным и однородным графом?



Приведите примеры однородных графов.



Что такое вершина графа?



Чем отличается вершина графа от ребра?



Какие известны высказывания связанные с понятием "вершина графа"?


Задачи

  1. Построить граф с заданными характеристиками
  2. К какому классу относится указанный граф
  3. Расчет числовых характеристик графа
  4. Проверить принадлежность графа к некоторому классу
  5. Поиск пути
  6. Поиск изоморфного подграфа в графе

прежде чем писать решение задачи на SCP, проверить, может ли она быть решена с помощью логической формулы текущей версией решателя.


определение принадлежности графа классу двудольных графов

Знания необходимые в базе знаний для ответа на вопрос:
определение двудольного(двураскрашиваемого, бихроматического) графа, определение доли, определение раскраски, k-раскрашиваемости, алгоритм проверки на k-раскрашиваемость(двураскрашиваемость, модификация алгоритма обхода в ширину/глубину)



определение принадлежности графа классу полных двудольных графов

Знания необходимые в базе знаний для ответа на вопрос:
определение полного двудольного(двураскрашиваемого, бихроматического) графа, определение двудольного графа, алгоритм проверки на k-раскрашиваемость, алгоритм проверки на полноту двудольного графа)



определение принадлежности графа классу полных графов

Знания необходимые в базе знаний для ответа на вопрос:
определение полного графа, алгоритм проверки на полноту графа)



определение возможности существования графа с заданными количеством и степенями вершин

Знания необходимые в базе знаний для ответа на вопрос:
по идее должно решаться решателем, но пока не может, по этому можно решать алгоритмом, решается на основе леммы о рукопожатиях)



определение компонент связности графа

Знания необходимые в базе знаний для ответа на вопрос:
определение компоненты связности графа, алгоритм обхода в ширину/глубину)



определение минимального числа рёбер и самих рёбер, удаление которых приведёт граф к двудольному

Знания необходимые в базе знаний для ответа на вопрос:
...)



определение максимального числа рёбер и самих рёбер, добавление которых к заданному двудольному графу оставит его двудольным(дополнение до полного двудольного графа)

Знания необходимые в базе знаний для ответа на вопрос:
...)



определение возможности существования двудольного графа по заданным степеням вершин в каждой из долей

Знания необходимые в базе знаний для ответа на вопрос:
теорема о равенстве сумм степеней вершина в долях двудольного графа)



определение числа дуг орграфа по заданным степеням захода/исхода вершин

Знания необходимые в базе знаний для ответа на вопрос:
...)



поиск маршрута

Знания необходимые в базе знаний для ответа на вопрос:
определение маршрута, алгоритм обхода в ширину-глубину)



поиск кратчайшего пути

Знания необходимые в базе знаний для ответа на вопрос:
определение кратчайшего пути, алгоритм Дейкстры)



определение принадлежности графа классу эйлеровых

Знания необходимые в базе знаний для ответа на вопрос:
определение эйлерового графа)



определение минимального дополнения рёберами до эйлерового графа

Знания необходимые в базе знаний для ответа на вопрос:
...)



определение принадлежности графа классу уникурсальных графов

Знания необходимые в базе знаний для ответа на вопрос:
определение уникурсального графа)



решение задача коммивояжера (NP-полная)

Знания необходимые в базе знаний для ответа на вопрос:
полнопереборный алгоритм)



определение принадлежности графа к классу планарных

Знания необходимые в базе знаний для ответа на вопрос:
теорема Понтрягина-Куратовского или алгоримт)



доказательство не принадлежности графа к классу планарных с помощью теоремы Эйлера

Знания необходимые в базе знаний для ответа на вопрос:
теорема Эйлера)



Личные инструменты