gs 1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci


GRAFY I SIECI. Zadania domowe 1.

  1. Niech X = { 2, 3, 4, 5, 6, 7 }.

W zbiorze X wprowadzamy relację x R y ⇔ y mod x = 1. Dla zbioru X i relacji określonej powyżej podaj macierz sąsiedztwa grafu (skierowanego) tej relacji. Podaj stopnie wierzchołków i sprawdź lemat o sumie stopni wierzchołków. Następnie wyznacz graf pochodny, przez podanie jego macierzy sąsiedztwa. Także podaj stopnie wierzchołków i sprawdź lemat o sumie stopni dla grafu pochodnego.

2. Niech M =

będzie macierzą sąsiedztwa grafu skierowanego (G, A). Oblicz stopnie wierzchołków i sprawdź twierdzenie o ich sumie. Czy graf ten jest silnie spójny? Odpowiedz bez rysowania. Wyznacz graf pochodny tego grafu i jego macierz sąsiedztwa. Czy graf pochodny jest spójny?

  1. Narysuj graf (nieskierowany) o czterech wierzchołkach, który jest izomorficzny ze swoim grafem dopełniającym. Opisz oba grafy macierzami incydencji.

  1. Narysuj graf (nieskierowany) o czterech wierzchołkach, który jest izomorficzny ze swoim grafem krawędziowym. Opisz oba grafy macierzami incydencji.

  1. Narysuj graf krawędziowy grafu K4,1. Czy jest to graf dwudzielny, czy jest planarny?

  1. Czy poniższe grafy są izomorficzne:

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

  1. Dla grafu o podanej macierzy sąsiedztwa sprawdź czy jest on

  1. Spójny

  2. Dwudzielny

0x08 graphic
0x08 graphic
0 0 1 0 1 0 1

0 0 0 1 0 1 1

M = 1 0 0 1 1 1 0

0 1 1 0 0 0 0

1 0 1 0 0 0 0

0 1 1 0 0 0 0

1 1 0 0 0 0 0

  1. Ile jest drzew o pięciu wierzchołkach {1, 2, 3, 4, 5} mających

  1. wierzchołek stopnia 4,

  2. wierzchołek stopnia 3.

  1. Dany jest graf spójny o trzech wierzchołkach stopnia 4 i ośmiu wierzchołkach stopnia 1. Czy graf ten jest drzewem? Czy jest dwudzielny?

  1. Narysuj graf o 8 wierzchołkach i 5 składowych spójnych, który ma maksymalną ilość krawędzi.

  1. Narysuj graf o 8 wierzchołkach i 2 składowych spójnych, w którym stopnie wierzchołków wynoszą: 1, 1, 2, 1, 1, 1, 2, 1 albo uzasadnij, że taki graf nie istnieje.

  1. Ile składowych spójnych może mieć graf o n = 7 wierzchołkach i m = 6 krawędziach?

  1. Podaj przykład grafu o dwóch składowych spójnych, sześciu wierzchołkach i

  1. czterech krawędziach

  2. dziesięciu krawędziach

  1. Czy poniższe grafy są planarne?

0x01 graphic

a

b

e

d

c

z

u

v

y

x



Wyszukiwarka

Podobne podstrony:
gs 3, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci
gs 2, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci
zad6 i 7 grafy zdanka, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci
zad11 grafy zdanka, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci
zestaw4 popr, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci
zad9 grafy zdanka, wisisz, wydzial informatyki, studia zaoczne inzynierskie, grafy i sieci
11-nkb~1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l2
2-eukl~1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l2
1-algo~1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l2
c-zadania-w3, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, kol
2-eukl~1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l2
x, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, kol 1
pytanie4, wisisz, wydzial informatyki, studia zaoczne inzynierskie, statystyczne metody wspomagania
minmax3, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l6
KomprKrz, wisisz, wydzial informatyki, studia zaoczne inzynierskie, przetwarzanie obrazow
2-eukl~1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l2
cwicz6, wisisz, wydzial informatyki, studia zaoczne inzynierskie, sieci komputerowe
2-eukl~1, wisisz, wydzial informatyki, studia zaoczne inzynierskie, podstawy programowania, l2

więcej podobnych podstron