ОСНОВНЫЕ ПОНЯТИЯ И ОПЕРАЦИИ

К расходам и доходам будущих периодов относятся такие операции, которые предполагают получение доходов или осуществление расходов в одном отчётном периоде, но относящихся к другому отчётному периоду. Неправильное их отражение может привести к искусственному завышению или занижению прибыли предприятия, а значит к нарушению принципа соответствия доходов и расходов. Аудитор должен проверить имелись ли в отчётном периоде у предприятия такие доходы и расходы, подтверждались ли они производственной необходимостью и имеются ли первичные документы их подтверждающие.

К расходам, которые предприятие должно относить на будущие отчётные периоды относят:

1. расходы, связанные с подготовительными работами в сезонных предприятиях

2. расходы по освоению новых производств

3. авансовые арендные платежи

4. приобретение страхового полиса

5. подписка на периодические издания

6. оплата стоимости торговых патентов

Эти расходы должны учитываться на сч.39 «Расходы будущих периодов». И в момент их оплаты в зависимости от вида предприятие должно отразить:

· начисление амортизации оборудования использованного для освоения новых производств: Дт 39 - Кт 13

· использование запчастей, материалов для новых производств: Дт 39- Кт 20

· оплата труда работников по освоению новых производств: Дт 39- Кт 661,65

· перечисление средств за страховой полис, на подписку, на уплату авансовых арендных платежей: Дт 39 - Кт 311

По мере фактического осуществления этих расходов и получения от них доходов предприятие должно закрыть сч.39 и отразить затраты на соответствующем счёте 9 класса.

К доходам будущих периодов относятся:

1. авансовые платежи по аренде от арендаторов

2. стоимость подписки в отделениях связи

3. суммы оплаченных полисов в страховых компаниях

4. предоплата за путёвки

5. предварительная продажа билетов

Доходы будущих периодов должны учитываться на сч.69 и списываться на сч.79 по мере наступления соответствующего отчётного периода.

ОСНОВНЫЕ ПОНЯТИЯ И ОПЕРАЦИИ

Графы, их вершины, ребра и дуги. Теорию графов начали разрабатывать для решения некоторых задач о гео­метрических конфигурациях, состоящих из точек и линий. В этих задачах несущественно, соединены ли точки конфи­гурации отрезками прямых или криволинейными дугами, какова длина линий и другие геометрические характери­стики конфигурации. Важно лишь то, что каждая линия соединяет какие-либо две из заданных точек. Таким обра­зом, можно дать определение графа как совокупности двух множеств V (точек) и Е (линий), между элементами которых определено отношение инцидентности, причем каждый эле­мент е Е инцидентен ровно двум элементам v', v" V. Элементы множества V называются вершинами графа G, элементы множества E — его ребрами. Вершины и ребра графа G называют еще его элементами и вместо v V, е Е пишут соответственно V G и е G.

В некоторых задачах инцидентные ребру вершины не­равноправны, они рассматриваются в определенном по­рядке. Тогда каждому ребру можно приписать направление от первой из инцидентных вершин ко второй. Напра­вленные ребра часто называют дугами (однако в этой книге они будут называться ребрами), а содержащий их граф — ориентированным (граф, определенный ранее, называется неориентированным). Первая по порядку вершина, инци­дентная ребру ориентированного графа, называется его началом, вторая — его концом. Говорят еще, что ребро ориентированного графа выходит из начала и входит в ко­нец.

В дальнейшем оказалось, что понятие графа можно при­менить не только при исследовании геометрических конфи­гураций. Особенно часто определяют графы при анализе функционирования систем. С отдельными компонентами изучаемой системы удобно связывать вершины графа, а с па­рами взаимодействующих компонент — его ребра. Построен­ный таким образом граф называют структурным графом системы.

Изображение графов. На рис. 4-1, а—з изображены некоторые неориентированные графы. Множество ребер Е может быть пустым (см. рис. 4-1, г). Если же множество вершин V пусто, то пусто и Е. Такой граф называется пу­стым. Линии, изображающие ребра графа, могут пересе­каться, но точки пересечения не являются вершинами (см. рис. 4-1, д); различные ребра могут быть инцидентны одной и той же паре вершин (рис. 4-1, е), в этом случае они назы­ваются кратными; граф, содержащий кратные ребра, часто называют мультиграфом. Ребро может соединять некоторую вершину саму с собой (рис. 4-1, ж), такое ребро назы­вается петлей. На рис. 4-1,з изображен фрагмент беско­нечного графа. Его вершины — это точки плоскости с це­лыми координатами (х, y), а ребра — соединяющие их горизонтальные и вертикальные отрезки длины 1.

Обычно рассматриваемые графы конечны, т. е. конечны множества их элементов (вершин и ребер). Поэтому конеч­ность этих графов не будет специально оговариваться. Однако некоторые понятия и результаты, о которых будет идти речь, относятся к произвольным графам.

Рис. 4-2.

При изображении ориентированных графов (рис. 4-2,а—з) направления ребер отмечаются стрелками, примыкающими к их концам. Ориентированный граф также может иметь кратные ребра (рис. 4-2, е), петли (рис. 4-2, да), а также соединяющие одни и те же вершины ребра, идущие в про­тивоположных направлениях (рис. 4-2, з).

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

Матрица инцидентности и список ребер. Задать граф — значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф G — конечный, для описания его вершин и ребер достаточно их занумеровать. Пусть v₁, v₂, ..., v_n — вершины графа G; е₁, e₂, ..., е_т— его ребра. Отношение инцидентности можно определить матри­цей || ||, имеющей т строк и п столбцов. Столбцы соот­ветствуют вершинам графа, строки — ребрам. Если ребро e_i инцидентно вершине v_j, то = 1, в противном случае = 0. Это так называемая матрица инцидентности не­ориентированного графа G, которая является одним из способов его определения (для графа на рис. 4-3 она дана в табл. 4-1а).

Таблица 4-1

б)

в)

г)

В матрице инцидентности || || ориентированного гра­фа G, если вершина v_j— начало ребра a_i то = -1; если v_j— конец a_i, то = 1; если а_i— петля, а v_j — инцидентная ей вершина, то = , где — любое число, отличное от 1, 0 и —1, в остальных случаях = 0 (при­мер— табл. 4-16 для графа на рис. 4-4).

В каждой строке матрицы инцидентности для неориен­тированного или ориентированного графа только два эле­мента отличны от 0 (или один, если ребро является петлей). Поэтому такой способ задания графа оказывается недостаточно экономным. Отношение инцидентности можно еще задать списком ребер графа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инци­дентных ему. Для неориентированного графа порядок этих вершин в строке произволен, для ориентированного первым стоит номер или другое наименование начала ребра, а вто­рым— его конца. В табл. 4-1в и 4-1г приводятся списки ребер для графов, изображенных на рис. 4-3 и 4-4.

По списку ребер графа легко построить его матрицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером. Для не­ориентированного графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1, и для ориентированного графа в этой строке первым стоит номер элемента строки матрицы, равного -1, а вторым — номер элемента, равного +1.

Матрица смежности графа. Это квадратная матрица | | столбцам и строкам которой соответствуют вершины графа. Для неориентированного графа равно количеству ребер, инцидентных i-й и j-й вершинам, для ориентированного графа этот элемент матрицы смежности равен коли­честву ребер с началом в i-й вершине и концом в j-й. Таким образом, матрица смежности неориентированного графа сим­метрична ( = ), а ориентированного — не обязательно. Если она все же симметрична, то для каждого ребра ори­ентированного графа имеется ребро, соединяющее те же вершины, но идущее в противоположном направлении. Ориентированный граф с симметричной матрицей смежности канонически соответствует неориентированному графу, име­ющему ту же матрицу смежности.

Матрицы смежности рассмотренных ранее графов (рис. 4-3, 4-4) приводятся в табл. 4-2.

Таблиц 4-2

Матрица смежности также определяет соответствующий неориентированный или ориентированный граф. Число его вершин равно размерности матрицы п, i-й и j-й вершинам графа инцидентны ребер. Для неориентированного гра­фа = и все его ребра определяются верхним правым треугольником матрицы, расположенным над диагональю, включая последнюю. Количество их равно сумме по

этому треугольнику, т. е. . Ребра ориентированного графа определяются всеми элементами матрицы смеж­ности. В обоих случаях по матрице смежности легко строит­ся, например, список ребер, определяющий граф. Элементу матрицы смежности, расположенному в i-й строке и j-м столбце, соответствуют строк списка ребер (при = 0 — ни одной строки), в каждой из кото­рых записаны номера i, j. Для неориентированного графа эти строки соответствуют только элементам описанного ранее верхнего правого треугольника матрицы смежности, т. е. элементам с j i, а для ориентированного графа нужно рассматривать все элементы .

Идентификация графов, заданных своими представле­ниями. Итак, граф может быть представлен различными способами. Он может быть изображен на чертеже, задан матрицей инцидентности, списком ребер или матрицей Смежности. Вид чертежа зависит от формы линий и взаим­ного расположения вершин. Иногда не так легко понять, одинаковы ли графы, изображенные разными чертежами (ср., например, графы на рис. 4-5). Вид матриц и списка ребер зависит от нумерации вершин и ребер графа. Строго говоря, граф считается полностью заданным, если нумера­ция его вершин зафиксирована; графы, отличающиеся только нумерацией вершин, называются изоморфными.

Перенумерация вершин графа задается строкой , , ..., новых номеров вершин, расположенных в исход­ном порядке. Новая матрица смежности получается из исходной перемещением каждого элемента в -ю строку и -й столбец, т. е. в результате перестановки ( , , ..., )

строк и столбцов исходной матрицы. Поэтому, чтобы узнать, представляют ли две матрицы смежности изо­морфные графы, можно, на­пример, произвести всевоз­можные одинаковые пере­становки строк и столбцов первой матрицы. Если пос­ле одной из этих переста­новок возникнет матрица, тождественно совпадающая со второй, графы, изображае­мые данными матрицами смежности, изоморфны. Однако чтобы убедиться таким способом в том, что графы неизо­морфны, придется выполнить все n! перестановок строк и столбцов, что является достаточно трудоемкой опера­цией.

Матрица инцидентности графа и список его ребер зависят от нумерации ребер и вершин. Переход от одной пары ну­мерации к другой определяется перестановками ( , , ..., ) вершин и ( , , ..., ) ребер рассматриваемого графа. Матрица инцидентности получается из первоначаль­ной в результате перестановки строк (i-я — на -е место) и столбцов (j-й — на -е). Строки списка ребер переста­вляются так же, как и строки матрицы инцидентности, и каждый номер j в строках этого списка заменяется номе­ром .

Графы без кратных ребер. Пусть даны два множества V₁ и V₂ Их прямое произведение V₁ X V₂ можно симметризовать, т. е. рассматривать также пары (v₂, v₁), где v₂ V₂, а v₁ V₁, причем пары (v₁, v₂) и (v₂, v₁) считаются одинако­выми. Если v₁= V₂ = V, то несимметризованное произ­ведение V х V— это множество всех упорядоченных пар (v₁, v₂) элементов множества V, а симметризованное произ­ведение [V X V] — это множество неупорядоченных пар, когда (v₁, v₂) = (v₂, v₁).

Пусть Е — подмножество [V X V]. Тогда V можно счи­тать множеством вершин, а E — множеством ребер неориен­тированного графа [ребро (v₁, v₂) E инцидентно верши­нам v₁ и v₂. Аналогично подмножество Е' V X V опре­деляет ориентированный граф, в котором началом ребра (v₁, v₂) Е' является вершина v₁, a концом — вершина v₂. Каждая пара (v₁, v₂), принадлежащая подмножеству Е или Е', фигурирует в качестве ребра только один раз, следова­тельно, построенные графы не имеют кратных ребер и наоборот, если граф не имеет кратных ребер, то последние однозначно определяются неупорядоченной или упорядочен­ной парой (v₁, v₂) инцидентных им вершин. Поэтому множе­ства ребер неориентированного или ориентированного графа считаются подмножествами в первом случае симметризованного произведения, а во втором—несимметризованного.

Степени вершин графа. Пусть G — неориентированный граф. Количество (v) ребер, инцидентных вершине v G, называется ее локальной степенью или просто степенью.

Если степени всех вершин конечны, рассматриваемый граф G называется локально конечным. В частности, лю­бой конечный граф локально конечен.

Когда заданы матрицы смежности или инцидентности графа, можно определить локальные степени всех его вер­шин. Действительно, в j-м столбце, соответствующем вер­шине v_j, единицы стоят на пересечении со строками, кото­рым соответствуют инцидентные этой вершине ребра, а остальные элементы столбца равны 0. Следовательно,

(v_j) = . Элементы же матрицы смежности — это количество ребер, инцидентных вершинам v_i и v_j. Отсюда

(v_j) = .

При подсчете степеней вершин по этим формулам каждая петля дает в степень инцидентной ей вершины вклад 1. Однако при изображении петли на рисунке к этой вершине примыкают два конца петли, т. е. петля дает в эту степень вклад 2. Чтобы таким образом учитывать вклад петель в сте­пень, нужно несколько усложнить формулы для ее вычи­сления. Через коэффициенты матрицы инцидентности ее можно вычислить, например, по формуле

^/(v_j) = . Когда i-e ребро обычное,

и соответствующее слагаемое внешней суммы равно т. е. 1 для ребер, инцидентных вершине v_j, и 0 для остальных. Если же оно является петлей, то , а слагаемое внешней суммы равно 2 , т. е. 2 для петель, инцидентных вершине v_j, и 0 для остальных.

Это же значение степени выражается через коэффициенты матрицы смежности графа G формулой

^/(v_j) = .

В зависимости от рассматриваемой задачи может потре­боваться тот или иной способ определения степени вершины. Поэтому в каждом случае должно быть указано, является ли петля однажды или дважды инцидентной своей вер­шине.

Так как каждое ребро имеет два конца, в сумме

ребра учитываются по два раза. Таким образом, эта сумма равна удвоенному числу ребер графа, т. е. четна. Следова­тельно, четно и количество нечетных слагаемых этой суммы, т. е. число вершин нечетной степени.

Граф называется однородным степени k, если степени всех его вершин равны k и тем самым равны между собой. Если однородный граф степени k имеет n вершин и m ребер,

то , . Граф без кратных ребер называется полным, если каждая пара вершин сое­динена ребром.

Локальные степени ориентированных графов. Для вер­шин ориентированного графа определяются две локальные степени: ₁(v) — число ребер с началом в вершине v или, иначе, количество выходящих из v ребер, и ₂(v) — коли­чество входящих в v ребер, для которых эта вершина являет­ся концом. Петля дает вклад 1 в обе эти степени. Локальные степени вершин ориентированного графа просто выража­ются через коэффициенты его матрицы смежности: ₁(v_i) = .

Выражение их через коэффициенты матрицы инцидент­ности значительно сложнее. Так как каждое ребро ориентированного графа G имеет одно начало и один конец, суммы и

равны количеству ребер этого графа, а значит, и равны между собой. Отсюда следует, что в однородном ориентиро­ванном графе степени k с п вершинами и т ребрами m = = n = m/k.

Части, суграфы и подграфы. Граф H называется частью графа G, H G, если множество его вершин V (H) содер­жится в множестве V (G), а множество Е (H) ребер — в Е (G). Если V (H) = V (G), часть графа называется суграфом. Например, имеется нулевой суграф Æ (G), множество ребер которого пусто. Суграф H покрывает вершины неориенти­рованного графа G (или является покрывающим), если любая вершина последнего инцидентна хотя бы одному ребру из H. Таким образом, если в графе G есть изолированная вершина v, не инцидентная ни одному ребру, покрываю­щие суграфы этого графа не существуют.

Любое множество В ребер графа G можно считать мно­жеством ребер некоторой части H. Множество вершин этой части состоит из вершин, инцидентных элементам множе­ства В. Если В является множеством ребер другой части H', то H H', причем вершины H', не принадлежащие H, в графе H' изолированы.

Подграфом G (U) графа G с множеством вершин U V называется часть, которой принадлежат все ребра с обоими концами из U. Звездный граф для вершины v G состоит из всех ребер с началом или концом в вершине v. Множе­ство вершин звездного графа состоит из v и других, инци­дентных его ребрам вершин.

Операции с частями графа. Дополнение части H опре­деляется множеством всех ребер графа G, не принадлежа­щих H.

Сумма H₁ U H₂ и пересечение H₁ H₂ частей H₁ и H₂ графа G определяются естественно:

V(H₁ U H₂) = V(H₁) U V(H₂);

E(H₁ U H₂) = E(H₁) U E(H₂);

V(H₁ H₂) = V(H₁) V(H₂);

E(H₁ H₂) = E(H₁) E(H₂).

Две части H₁ и H₂ не пересекаются по вершинам, если они не имеют общих вершин, а значит, и общих ребер. Сумма Н₁ U H₂ не пересекающихся по вершинам частей называется прямой суммой. Аналогично определяется пря­мая сумма любого числа частей. Части Н₁ и H₂ не пересе­каются по ребрам, если Е(Н₁) Е(H₂) = Æ. Например, для любой части H и ее дополнения H сумма G = Н U Н — прямая по ребрам.