Лабораторная работа : Графы. Основные понятия 


Полнотекстовый поиск по базе:

Главная >> Лабораторная работа >> Математика


Графы. Основные понятия




Министерство образования и науки Российской Федерации

Курский государственный технический университет

Кафедра ПО ВТ и АС

Лабораторная работа № 1

Графы. Основные понятия

Выполнил: студент гр. ПО 62 Шиляков И.А.

Проверил: доцентТомакова Р.А.

Курск 2007

Задание:

  1. По заданным матрицам смежности вершин восстановить графы.

  2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

  3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.

  4. Найти композицию графов .

  5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

  6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

  7. Определить хроматические и цикломатические числа данных графов.

  8. Найти все базы графа.

  9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Выполнение:

  1. По заданным матрицам смежности вершин восстановить графы.

x1

x2

x3

x4

x5

x6

x7

x1

0

1

0

0

0

0

1

x2

0

0

1

0

0

1

0

x3

0

1

0

1

0

0

0

x4

1

0

0

0

1

0

0

x5

1

0

0

0

0

0

1

x6

0

0

1

1

0

0

0

x7

0

0

0

0

1

1

0

A1

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G1(X1,A1)

x1

x2

x3

x4

x5

x6

x7

x1

0

1

1

0

0

0

0

x2

0

0

0

1

1

0

0

x3

0

1

0

0

0

0

1

x4

1

0

0

0

1

0

0

x5

0

0

0

0

0

1

1

x6

1

0

0

1

0

0

0

x7

0

0

1

0

0

1

0

A2

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G2(X2,A2)

  1. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а1

0

1

1

1

1

0

1

0

1

0

0

0

0

0

а2

1

0

0

0

0

0

1

0

1

1

0

0

1

1

а3

1

0

0

1

1

1

0

0

0

0

1

0

0

0

а4

1

0

1

0

1

0

0

0

0

0

1

1

0

1

а5

1

0

1

1

0

1

0

0

0

0

1

0

0

0

а6

0

0

1

0

1

0

1

1

0

0

1

1

0

0

а7

1

1

0

0

0

1

0

1

1

0

0

1

0

0

а8

0

0

0

0

0

1

1

0

1

1

0

1

1

0

а9

1

1

0

0

0

0

1

1

0

1

0

0

1

0

а10

0

1

0

0

0

0

0

1

1

0

0

0

1

1

а11

0

0

1

1

1

1

0

0

0

0

0

1

0

1

а12

0

0

0

1

0

1

1

1

0

0

1

0

0

1

а13

0

1

0

0

0

0

0

1

1

1

0

0

0

1

а14

0

1

0

1

0

0

0

0

0

1

1

1

1

0

B1

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а1

0

1

0

1

1

1

1

0

1

0

0

0

0

0

а2

1

0

1

1

1

1

0

1

0

0

0

0

0

0

а3

0

1

0

1

0

0

1

1

0

0

0

1

1

0

а4

1

1

1

0

0

0

1

1

1

0

0

0

0

0

а5

1

1

0

0

0

1

0

0

0

1

1

0

0

0

а6

1

1

0

0

1

0

0

0

0

1

1

0

0

0

а7

1

0

1

1

0

0

0

0

1

0

0

1

1

0

а8

0

1

1

1

0

0

0

0

0

0

1

0

1

1

а9

1

0

0

1

0

0

1

0

0

1

0

1

0

1

а10

0

0

0

0

1

1

0

0

1

0

1

1

0

1

а11

0

0

0

0

1

1

0

1

0

1

0

0

1

1

а12

0

0

1

0

0

0

1

0

1

1

0

0

1

1

а13

0

0

1

0

0

0

1

1

0

0

1

1

0

1

а14

0

0

0

0

0

0

0

1

1

1

1

1

1

0

B2

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

x1

1

1

0

0

0

0

-1

0

-1

0

0

0

0

0

x2

-1

0

1

1

-1

0

0

0

0

0

0

0

0

0

x3

0

0

-1

0

1

1

0

0

0

0

-1

0

0

0

x4

0

0

0

0

0

-1

1

1

0

0

0

-1

0

0

x5

0

0

0

0

0

0

0

-1

1

1

0

0

-1

0

x6

0

0

0

-1

0

0

0

0

0

0

1

1

0

-1

x7

0

-1

0

0

0

0

0

0

0

-1

0

0

1

1


S1

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

x1

1

0

0

1

0

0

-1

0

-1

0

0

0

0

0

x2

0

-1

1

-1

0

0

0

1

0

0

0

0

0

0

x3

-1

1

0

0

-1

1

0

0

0

0

0

0

0

0

x4

0

0

-1

0

0

0

1

0

0

0

0

-1

1

0

x5

0

0

0

0

0

0

0

-1

0

0

1

0

-1

1

x6

0

0

0

0

0

0

0

0

1

-1

0

1

0

-1

x7

0

0

0

0

1

-1

0

0

0

1

-1

0

0

0


S2

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1


R1 R2

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

x1

x2

x3

x4

x5

x6

x7

x1

1

1

1

1

1

1

1

x2

1

1

1

1

1

1

1

x3

1

1

1

1

1

1

1

x4

1

1

1

1

1

1

1

x5

1

1

1

1

1

1

1

x6

1

1

1

1

1

1

1

x7

1

1

1

1

1

1

1

Q1 Q2

  1. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.

Объединение графов

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G3(X3,A3)=G1(X1,A1) YG2(X2,A2); X3= X1YX2, A3= A1YA2

Пересечение графов

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G3(X3,A3)=G1(X1,A1) ∩G2(X2,A2); X3= X1∩X2, A3= A1∩A2

Кольцевая сумма графов

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G3(X3,A3)=G1(X1,A1)G2(X2,A2)

  1. Найти и построить композицию графов .

G1(Х)

G2(Х)

G1(G2))

G2(G1))

x1

(x1,x2), (x1,x7)

(x1,x2), (x1,x3)

(x1,x3), (x1,x6),

(x1,x2), (x1,x4),

(x1,x4), (x1,x5),

(x1,x3), (x1,x6),

x2

(x2,x3),

(x2,x6)

(x2,x4),

(x2,x5)

(x2,x1), (x2,x5),

(x2,x7),

(x2,x2), (x2,x7),

(x2,x1), (x2,x4),

x3

(x3,x2),

(x3,x4)

(x3,x2),

(x3,x7)

(x3,x3), (x3,x6),

(x3,x5),

(x3,x4), (x3,x5),

(x3,x1),

x4

(x4,x1), (x4,x5)

(x4,x1), (x4,x5)

(x4,x2), (x4,x7),

(x4,x1),

(x4,x2), (x4,x3),

(x4,x6), (x4,x7),

x5

(x5,x1), (x5,x7)

(x5,x6), (x5,x7)

(x5,x3), (x5,x4),

(x5,x5), (x5,x6),

(x5,x2), (x5,x3),

(x5,x6),

x6

(x6,x3),

(x6,x4)

(x6,x1),

(x6,x4)

(x6,x2), (x6,x7),

(x6,x1), (x6,x5),

(x6,x2), (x6,x7),

(x6,x1), (x6,x5),

x7

(x7,x5), (x7,x6)

(x7,x3), (x7,x6)

(x7,x2), (x7,x4),

(x7,x3),

(x7,x6), (x7,x7),

(x7,x1), (x7,x4),

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000G1(G2))

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G2(G1))

  1. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

Остовные подграфы

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G1(X1,A1)

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G2(X2,A2)

Произвольные подграфы

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G1 (X1,A1)

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G2’’ (X2’’,A2’’)

Порожденные подграфы

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

G1P(X1P,A1P) G2P(X2P,A2P)

  1. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

Локальные степени графа G1

11)=2 ; 21)=2 ; 1)=4 ;

12)=2 ; 22)=2 ; 2)=4 ;

13)=2 ; 23)=2 ; 3)=4 ;

14)=2 ; 24)=2 ; 4)=4 ;

15)=2 ; 25)=2 ; 5)=4 ;

16)=2 ; 26)=2 ; 6)=4 ;

17)=2 ; 27)=2 ; 7)=4 ;

Локальные степени графа G2

11)=2 ; 21)=2 ; 1)=4 ;

12)=2 ; 22)=2 ; 2)=4 ;

13)=3 ; 23)=2 ; 3)=4 ;

14)=2 ; 24)=2 ; 4)=4 ;

15)=2 ; 25)=2 ; 5)=4 ;

16)=2 ; 26)=2 ; 6)=4 ;

17)=2 ; 27)=2 ; 7)=4 ;

Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.

Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.

  1. Определить хроматические и цикломатические числа данных графов.

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

Хроматическое число γ для графа G1 = 4

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

Хроматическое число γ для графа G2 = 4

Цикломатические числа графов

V(G1)=m-n+r, где m - число рёбер (дуг);

n – число вершин;

r – число компонент связности.

V(G1)=14-7+1=8;

V(G2)=14-7+1=8;

  1. Найти все базы графа.

Базы графа G1

B1={x1}

B2={x2}

B3={x3}

B4={x4}

B5={x5}

B6={x6}

B7={x7}

Базы графа G2

B1={x1}

B2={x2}

B3={x3}

B4={x4}

B5={x5}

B6={x6}

B7={x7}

  1. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Сильные компоненты связности G1

СК={x1, x2, x3, x4, x5, x6, x7}

Сильные компоненты связности G2

СК={x1, x2, x3, x4, x5, x6, x7}

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d0100000300000000000100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010009f30000000001000000180300000000000018030000010000006c000000000000000000000008000000100000000000000000000000a41f0000b80b000020454d4600000100180300001200000002000000000000000000000000000000000500002003000040010000c800000000000000000000000000000000e20400400d0300160000000c000000180000000a00000010000000000000000000000009000000100000004401000078000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000f1ffffff00000000000000000000000090010000000000cc04400022430061006c006900620072006900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100b0ae11001000000014b2110094af11005251603214b211000caf1100100000007cb01100f8b111002451603214b211000caf11002000000049642f310caf110014b2110020000000ffffffffcc43d300d0642f31ffffffffffff0180ffff01809f020180ffffffff00a907000008000000080000014a250001000000000000006000000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c0069006200720000000000410e0000d4af1100dee32e31e88d083234b3110040af11009c38273106000000010000007caf11007caf1100e878253106000000a4af1100cc43d3006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c00000000000002540000005400000000000000000000000800000010000000010000000000c8410000c841000000000d000000010000004c000000040000000000000000000000440100007800000050000000200008000900000046000000280000001c0000004744494302000000ffffffffffffffff4501000079000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0278004401040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f1ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000004401780020390900040000002d010000040000002d010000030000000000

Конденсация графа G1 Конденсация графа G2

Похожие работы: