Witam, będę bardzo wdzięczna za odpowiedź (i wyjaśnienie) na pytanie:
Czy 15-kostka ma 3-faktor?
teoria grafów
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
teoria grafów
\(\displaystyle{ 3}\) - faktor to graf \(\displaystyle{ 3}\)-regularny.
Każdy wierzchołek tej kostki ma przypisany binarny numer \(\displaystyle{ 15}\)-cyfrowy.
Bierzemy podgraf tej kostki składający się z wierzchołków które mają np. same \(\displaystyle{ 0}\) na pozycjach od \(\displaystyle{ 4}\) do \(\displaystyle{ 15}\) i dowolne wartości na pozycjach \(\displaystyle{ 1}\) do \(\displaystyle{ 3}\) i krawędziach między nimi. Wtedy dowolny wierzchołek tego podgrafu ma stopień \(\displaystyle{ 3}\), bo wychodzą z niego \(\displaystyle{ 3}\) krawędzie zmieniające wartości na pozycjach \(\displaystyle{ 1}\) do \(\displaystyle{ 3}\). Tak więc ta kostka ma taki faktor.
Każdy wierzchołek tej kostki ma przypisany binarny numer \(\displaystyle{ 15}\)-cyfrowy.
Bierzemy podgraf tej kostki składający się z wierzchołków które mają np. same \(\displaystyle{ 0}\) na pozycjach od \(\displaystyle{ 4}\) do \(\displaystyle{ 15}\) i dowolne wartości na pozycjach \(\displaystyle{ 1}\) do \(\displaystyle{ 3}\) i krawędziach między nimi. Wtedy dowolny wierzchołek tego podgrafu ma stopień \(\displaystyle{ 3}\), bo wychodzą z niego \(\displaystyle{ 3}\) krawędzie zmieniające wartości na pozycjach \(\displaystyle{ 1}\) do \(\displaystyle{ 3}\). Tak więc ta kostka ma taki faktor.