Konstrukcje algorytmiczne nieujemnych grafów krawędziowo-dwudzielnych oraz kongruencji macierzy Grama

Abstract

Rozprawa jest poświęcona wybranym problemom algorytmicznym i obliczeniowym występujących w klasyfikacji Grama dodatnio określonych oraz dodatnio półokreślonych głównych całkowitych jednorodnych funkcjonałów kwadratowych, a także klasyfikacji Coxetera-Grama dodatnich oraz głównych grafów krawędziowo-dwudzielnych bez pętli o skończonym zbiorze wierzchołków oraz skończonym zbiorze krawędzi oznakowanych symbolami z dwuelementowego zbioru {+,-}. Jednym z głównych celów tej pracy jest zbudowanie narzędzi algorytmicznych do rozwiązywania wybranych problemów spektralnej klasyfikacji Coxetera nieujemnych grafów krawędziowo-dwudzielnych bez pętli. W rozprawie przedstawiamy m.in. konstrukcję klasy algorytmów kombinatorycznych i numerycznych pozwalających rozwiązywać problemy spektralnej klasyfikacji Coxetera grafów krawędziowo-dwudzielnych bez pętli.