Ф

Фактор графа - то же, что и Остовный подграф.

n-фактор графа(n-factor of a graph)
- регулярный остовный подграф степени n.
Литература:[Харари]

Фактор-граф(Factor-graph)
- пусть в графе выделены максимальные непересекающиеся подграфы заданного вида; тогда Ф.-г. есть граф, получаемый из исходного стягиванием указанных подграфов в отдельные вершины.
См. Граф Герца, Зонно-интервальное представление уграфа.
Литература:[Евстигнеев]

Фактор-уграф(Factor-control-flow-graph)
- уграф G', который получается из исходного уграфа G стягиванием некоторого непустого множества попарно непересекающихся альтов R в вершины (обозначается G'=R(G)). Начальной (соответственно конечной) вершиной уграфа G' является либо начальная (соответственно конечная) вершина уграфа G, либо тот альт из R, который содержит начальную (соответственно конечную) вершину исходного уграфа.
Литература:[Касьянов]

f-фактор(f-factor)
- для заданной целочисленной функции f, определенной на вершинах графа G, такой суграф H графа G, что степень d[_H](x) = f(x) для каждой вершины x [include] V(G).
Литература:[Татт]

Факторизация графа(Factorization of a graph)
- разложение графа на непересекающиеся по ребрам n-факторы.
Литература:[Харари]

n-факторизация графа(n-factorization of a graph)
- разложение графа на непересекающиеся по ребрам n-факторы.
Литература:[Харари]

n-факторизуемый граф(n-factorizable graph)
- граф, допускающий n-факторизацию.
Литература:[Харари]

Формальный язык(Formal language)
- любое подмножество цепочек в некотором алфавите.
Язык

L[_1] L[_2] = {xy : x [include] L[_1] , y [include] L[_2] }
называется конкатенацией (а также сцеплением, или произведением) языков L[_1] и L[_2].
k-итерация языка L, обозначаемая через L[^k], определяется по правилам:
1) L[^0]={e}, где e - пустая цепочка,
2) L[^k]=LL[^k-1] для любого k > 0.
Позитивная итерация языка L, обозначаемая через L[^+], - это язык, получаемый объединением языков L[^k] для всех k [geq] 1; язык L[^*]=L[^+] [cup] L[^0] называется итерацией языка.
Литература:[Касьянов-Поттосин],[Евстигнеев-Касьянов]

Формула Эйлера(Euler's formula)
- формула, связывающая число вершин n, число ребер m и число граней f в выпуклом многограннике и плоском графе:

n + f - m = 2.

Литература:[Лекции]

Фрагмент(Fragment)
- любая часть уграфа. Фрагмент C является подфрагментом фрагмента S, если C - часть S. Подфрагмент C фрагмента S, отличный от S, называется собственным подфрагментом.
    Вершина p фрагмента C называется начальной (соответственно выходной), если либо p - начальная (соответственно конечная) вершина уграфа, либо в p заходит (соответственно из p исходит) дуга уграфа, не принадлежащая C. Вершина p фрагмента C называется входной (или входом), если существует путь по уграфу от его начальной вершины до p, не содержащий дуг C. Вершина p называется конечной для фрагмента C, если она не принадлежит C и является преемником хотя бы одной его вершины.
     Вершина p фрагмента C, отличная от начальной и конечной вершин уграфа, называется граничной вершиной C, если p является начальной или выходной вершиной C. Граничная вершина p фрагмента C называется стартовой, если в нее не заходят дуги фрагмента C или из нее не исходят дуги, не принадлежащие C, и финишной, если в нее заходят лишь дуги фрагмента C или из нее не исходят дуги, принадлежащие C.
     Фрагмент называется правильным, если он имеет в точности две граничные вершины, одна из которых - стартовая, а вторая - финишная. Правильный фрагмент называется простым, если он содержит одну дугу.
     Правильный фрагмент, не являющийся простым, называется первичным, если все его собственные правильные подфрагменты являются простыми.
См. Альт, Гамак, Зона, Интервал, Линейная компонента, Линейный участок, Луч.
Литература:[Касьянов],[Евстигнеев-Касьянов]

Фундаментальная система разрезов(Fundamental set of cutsets)
- относительно данного каркаса T множество разрезов, определяемых удалением ребер каркаса; каждый такой разрез содержит ровно одно ребро каркаса T.
Литература:[Уилсон], [Welsh]

Фундаментальная система циклов(Fundamental set of circuits)
- относительно данного каркаса T множество циклов, определяемых добавлением к каркасу ровно одной хорды каркаса T.
Литература:[Уилсон]

Фундаментальный цикл(Fundamental circuit)
- 1) относительно данного каркаса T в графе G цикл, однозначно определяемый добавлением к каркасу одной хорды e [include] E(G) \ E(T);
2) относительно базы B матроида M = (S,[ii]) и элемента x [include] S \ B цикл, однозначно определяемый добавлением к базе элемента x [include] S \ B.
Литература:[Уилсон], [Welsh]

Функциональная вершина(Functional vertex)
- та вершина помеченного ациклического графа, представляющего некоторый терм, которая помечена символом функции.
Литература:[Евстигнеев-Касьянов]

Функциональный орграф(Functional directed graph)
- орграф, у которого полустепень исхода каждой вершины равна 1; двойственный к нему орграф называется контрафункциональным орграфом.
Литература:[Харари]

Функция связности(Connectivity function)
- функция f, определяемая парами связностей графа G и отображающая множество {0, 1, ..., [kappa]}, где [kappa] - вершинная связность графа G, в множество Z неотрицательных целых чисел и такая, что f([kappa]) = 0.
Литература:[Харари]