Matematyka dyskretna 1/Ćwiczenia 15: Metody algebraiczne w teorii grafów

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Metody algebraiczne w teorii grafów

Ćwiczenie 1

Średnica spójnego grafu , to maksymalna odległość między parą wierzchołków zawartych w . Pokaż, że gdy jest grafem spójnym o średnicy , to zbiór macierzy jest liniowo niezależny.

Wskazówka
Rozwiązanie

Ćwiczenie 2

Pokaż, że prosty graf dwudzielny o niezerowym wyznaczniku i w którym ma skojarzenie doskonałe.

Wskazówka
Rozwiązanie

Ćwiczenie 3

Znajdź wszystkie wartości własne grafów oraz .

Wskazówka
Rozwiązanie

Ćwiczenie 4

Udowodnij, że w grafie prostym mamy wtedy i tylko wtedy, gdy któraś spójna składowa grafu jest grafem regularnym stopnia .

Wskazówka

Ćwiczenie 5

Pokaż, że jeśli jest wartością własną dwudzielnego grafu , to także jest wartością własną grafu .

Wskazówka

Ćwiczenie 6

Udowodnij, że w spójnym grafie prostym , liczba jest wartością własną macierzy wtedy i tylko wtedy, gdy jest regularnym grafem dwudzielnym stopnia .

Wskazówka