Теория графов – это раздел математики, включающий в себя систему терминов и обозначений, которые позволяют сравнительно просто описывать сложные процессы и явления.
Задача Эйлера заключается в том, чтобы пройти по семи мостам только один раз и вернуться в исходную часть города. Само название граф предполагает графическую интерпретацию изучаемого явления. Графом G=(X;U) называется совокупность двух множеств непустого множества X вершин и множеств U ребер, т.е.:
G=(X;U)= ,X≠0 U= , k=
Обычно граф изображают диаграммой, вершины – точками либо кружочками, а ребра – линиями. Если ребра графа ориентированы, т.е. показаны стрелкой от вершины к вершине, то они называются дугами, а такой граф называется ориентированным или орграфом (рис1). Если ребра не имеют ориентации, то граф называется неориентированным илинеографом (рис.2).
Рис.1 Рис.2
Каждая дуга соединяет две вершины графа, одна из которых является начальной, а другая – конечной и направлена от первой ко второй, дуги можно обозначать следующим образом:
Другим обозначением орграфа является задание множества вершин Х и соответствия Г( . Соответствие Г показывает, как между собой связаны вершины и называются отображением множества ХвХ, а граф обозначается G=(ХГ).
Для орграфа соответствие Г( , т.е. вершины , являются конечными вершинами дуг, у которых начальной вершиной будет
Г =
Г( ) = (
Г( = ø
Г( ) =
В случае неографа предполагается, что соответствие Г задает такой ориентированный граф, который получится из исходного графа заменой каждого ребра двумя противоположного направленными дугами, соединяющими те же вершины.
Например:
Г( )=( )
Так как Г( ) представляет множество вершин , для которых G существует дуга ( ), то через ( ) обозначает множество вершин , для которых в графе существует дуга ( ) и её называют обратным соответствием.
Например: для орграфа G(рисунок 3)
Если отображение Г( ) распространяется не на одну вершину, а множество вершин , а под множеством Г( ) понимают объединение Г( )U Г( )U… U Г( ) для орграфа (рисунок 3) оно будет выглядеть так:
Г({ })= { }, Г({ })={ }
Отображение Г(Г( ))→ ( ), а тройное отображение Г(Г(Г( )))→ ( ) и так далее.
Для нашего орграфа (рисунок 3)
( )= Г(Г( ))= Г({ }={ }
( ) Г( ( ))=Г({ })={ }
С каждой вершиной графа связано два множества:
( )- это множество тех, смежных – вершин, в которых заходят в дуги из .
( )- это множество таких вершин смежных , из которых выходят дуги, заканчивающиеся .
Вершины и называются смежными если существует дуга(ребро) U( ), соединяющая их.
Например ( ), ( ), ( ), вершины ( ) нашего (рисунок 1)орграфа, не являются смежными.
Если вершины и являются концами дуги, то говорят, что эти вершины инцидентныдугеU или дуга U инцидентна вершинам и .
Степенью или валентностью вершины графа называется количество инцидентных ей дуг и обозначается d( )= Г( ).
Вершина, степень которой равна нулю называетсяизолированной.
Число дуг орграфа, который имеет вершину своей начальной вершиной называется полустепеньюисхода и обозначается ( ).
Аналогично количество дуг орграфа, который имеет вершину конечнойвершины называется полустепеньюзахода и обозначается .
Например, для нашего рисунка 1
( )=3, ( )=1, ( )=1, ( )=2
Теорема Эйлера
Сумма степеней вершин графа ровна удвоенному количеству дуг или рёбер
Где n- число вершин графа,
m –число дуг.
Следствие №1
Число вершин нечётной степени всегда чётное.
Следствие №2
Сумма полу степеней вершин орграфа равна удвоенному числу дуг
Путем или ориентированным маршрутом орграфа называется последовательность дуг, в котором конечная вершина любой дуги отличной от последней является начальной вершиной следующей. Для нашего примера (рисунок 1) пути из вершины в вершину .
=
Ориентированнойцепью (орцепью) или простымпутём называется такой путь, в котором каждая вершина графа используется не более одного раза.
Маршрут – это неориентированный « двойник» пути. Это понятие рассматривается в тех случаях, когда можно пренебречь направленностью в орграфе.
Маршрут – это последовательность рёбер , , …, , в котором каждое ребро , за исключением первого и последнего ребра связано с ребрами и своими двумя концевыми вершинами.
Последовательность дуг в орграфе (рисунок 1)
Являются маршрутными.
Черта под дугой указывает исключение ориентации, то есть дуги рассматриваются как рёбра.
Маршруты бывают:
· простые и цепи(ребро в таком маршруте используется только один раз)
· элементарный (простые цепи)- в котором вершины встречаются только один раз.
Маршрут -простой, -цепь, - ни цепь и ни простой
Петлёй называется дуга графа, у которой начальной и конечной точки вершины совпадают (рисунок 1, ).
Путь ,…., называется замкнутым, если в нём конечная вершина дуги совпадает с начальной вершиной дуги .
Замкнутые пути орграфа называются контурами.
Замкнутые маршруты (цепи) в неографах называются циклами.
Тема 1: Финансы как исторически-экономическая категория
1. Экономическая сущность финансов
Финансы являются важнейшей экономической категорией, отражающей экономическое отношения в процессе создания и использования денежных средств.
Финансовые отношения многообразны, возникают на всех стадиях общественного процесса, на всех уровнях хозяйствования, во всех сферах общественной деятельности . Особенность этих отношений в том, что они всегда имеют денежную форму финансовой науки. Различаю два основных этапа развития финансов:
· Неразвитая форма финансов, которой был присущ непроизводственный характер, а основная масса денежных , а именно 2/3 бюджета расходовались на военные нужды и не оказали воздействия на экономику. Характерна узость финансовой системы, которая состояла из 1-го звена, т.е. государственного бюджета.
· Характерна многозвенность финансовой системы и высокой степенью воздействия на экономику большим разнообразием денежных отношений. Финансы становятся одним из важнейших орудий, воздействия на отношения воспроизводства, т.е. воспроизводство материальных отношений, вопросы финансовой науки имеются в работах мыслителей древнего мира Ксенофонта и Аристотеля. Среди мыслителей важное место занимает Фома Аквинский. Вместе с тем сама финансовая теория возникает в XVI в. В период зарождения капитализма. Связь финансов и государства привела к тому что, длительное время науки о государстве и только в XIX в. Получила самостоятельность, а во 2-ой половине XX теория финансов признается частью экономической теории.
Сущность финансов, как экономической категории состоит в том, что финансы всегда имеет денежную форму выражения, отражаются в процессе движения денег в наличных и безналичных формах и кроме этого движение всех инвестиционных ценностей заменяющих в определенный момент денежные средства.
Финансы (от лат. Finansia, перевод. денежные потоки или наличность )- это экономические отношения связанные с формированием распределением и использованием централизованных, децентрализованных фондов денежных средств в целях выполнения функций и задач, целей государства и обеспечения условий расширенного производства.
Финансовые отношения многообразны и возникают между:
1. между хозяйствующими субъектами в процессе преобразования темпции, между предприятием и реализуемыми товарами и услугами.
2. между предприятием и вышестоящими организациями при создании централизованных фондов
3. между государством и хозяйствующими субъектами при уплате ими налогов или финансовых платежей
4. между отдельными бюджетными и внебюджетными фондами
5. внутри хозяйствующих субъектов при формировании целевых фондов денежных средств финансового отношения при страхования организаций и населения
6. между гражданами централизованными бюджетными фондами при внесении платежей , ресурсов, а также при получении социальных трансфертов