21.04.2005

O klasie grafów lokalnie generowalnych i redukowalnych

Graf jest lokalnie generowalny wg pewnej reguły jeśli startując z grafu jednostkowego daje się go wyprowadzić dodając nowe wierzchołki zgodnie z pewna lokalna regułą i jest lokalnie redukowalny, jeśli usuwając z grafu wierzchołki zgodnie z zadaną regułą dotyczącą ich sąsiedztwa dojdzie się koniec końców do grafu jednostkowego. Reguła dotycząca generowania różni się zazwyczaj od reguły redukowania grafów sprawiającej naogół istotne trudności.

Tym problemom poświęcona jest omawiana prezentacja. Przedstawiona zostanie klasa grafów lokalnie generowalnych będąca równocześnie klasa grafów redukowalnych według tej samej reguły, przyczym klasa ta obejmuje wszystkie dotychczas znane typy grafów: drzewa, grafy pełne, trójkątne, centralne, a ponadto jest od nich istotnie szersza. Pokazane będą podstawowe własności grafów z tej klasy. Przyjęta reguła jest przytym najbardziej "liberalna" spośród dotychczas znanych reguł wyprowadzania, ale na tyle "restrykcyjna", aby zapewnić skuteczność redukcji.

Proces redukcji (generowania) ma dość przejrzysta interpretacje jako proces negocjacji, stad związek przedmiotu prezentacji ze strukturalnymi uwarunkowaniami procesów negocjacyjnych. Lokalność omawianych transformacji rzuca również pewne światło na ogólne zasady przetwarzania rozproszonego.