witam, mam pytanie (może i głupie), co oznacza sformułowanie, że dany graf jest bez 4-cykli?
czy tzn,że dany graf nie ma cykli długości 4, czy może że ten graf ma mniej niż 4 cykle?
proszę o odpowiedź
grafy planarne
grafy planarne
dziękuję, ale w związku z tym mam kolejne pytanie.
Muszę udowodnić następujące tw:
Jeżeli spójny płaski graf G, taki że \(\displaystyle{ \delta (G) \ge 3}\) jest grafem bez 4-cykli, to zachodzi jeden z następujących warunków:
1) istnieje krawędź xy taka, że \(\displaystyle{ deg_{G}x + deg_{G} y \le 7}\)
2)istnieje 4-wierzchołek v , ktory jest incydentny z dwiema nieprzyległymi 3-ścianami \(\displaystyle{ f_{1}=[v v_{1} v_{2}]}\) i \(\displaystyle{ f_{2}=[v v_{3} v_{4}]}\) takimi, że \(\displaystyle{ deg_{G} v_{i} \ge 4}\) dla i=1,2,3,4 oraz w zbiorze \(\displaystyle{ \{v_{1}, v_{2}, v_{3}, v_{4} \}}\) jest co najwyżej jeden wierzchołek stopnia większego niż 4.
Dowód przeprowadzam następująco:
załóżmy, że tw nie jest prawdziwe. Stosując klasyczny wzór Eulera\(\displaystyle{ \left| V(G)\right|-\left| E(G)\right| + \left| F(G)\right| =2}\) oraz lematy o uściskach dłoni dla wierzchołków i ścian otrzymujemy:
\(\displaystyle{ \sum_{v \in V(G)} (2 deg_{G} v -6)+ \sum_{f \in F(G)} (deg_{G} f - 6)= -12.}\)
(nie rozumiem tutaj tych kroków jak z tych lematów i wzoru eulera korzystamy, że powstaje taki wzór...proszę o wytłumaczenie:/)
Dalej niech \(\displaystyle{ w(x)= \begin{cases} 2 deg_{g} x - 6 dla x \in V(G) \\ deg_{g} x - 6 dla x \in F(G)\end{cases}}\) będzie waga wierzchołka x, wtedy możemy zapisać (początkowy wzór) nastepująco: \(\displaystyle{ \sum_{x \in V(G) \cup F(G)} w(x)= -12.}\)
To oznacza, że ogólna suma wag jest liczbą ujemną. Wprowadźmy pewną szczególną wymianę taką, że ogólna suma wag jest niezmieniona, ale funkcja wagowa jest nieujemna dla wszystkich \(\displaystyle{ x \in V(G) \cup F(G)}\). Zatem \(\displaystyle{ 0 \le \sum_{x \in V(G) \cup F(G)} w'(x)= \sum_{x \in V(G) \cup F(G)} w(x)= -12,}\) co jest sprzecznością. (tutaj też byłabym wdzięczna za pomoc, bo nie wiem sjądpóźniej nagle bierze się mi w'(x) ? )
Teraz zdefiniujemy zasady wymiany( których też nie rozumiem....
)
R1 : jeżeli \(\displaystyle{ deg_{G} v=4}\), toprzenosimy 1 z v do każdej incydentnej {4,4,4}-ściany w \(\displaystyle{ F_{3}(v)}\), \(\displaystyle{ \frac{3}{4}}\) do każdej incydentnej {4,4,t}-ściany gdzie \(\displaystyle{ t > 4}\)
oraz \(\displaystyle{ \frac{1}{4}}\) do każdej 5-ściany w \(\displaystyle{ F_{5}(v)}\).
R2 : jeżeli \(\displaystyle{ deg_{G} v > 4}\) to przenosimy \(\displaystyle{ \frac{3}{2}}\) z v do każdej 3-ściany w \(\displaystyle{ F_{3}(v)}\), i \(\displaystyle{ \frac{1}{3}}\) do każdej 5-ściany w \(\displaystyle{ F_{5}(v)}\).
Pozostało pokazać, ze funkcja wagi w'(x) jest nieujemna dla każdego \(\displaystyle{ x \in V(G) \cup F(G)}\). Trzeba to wykazać zgodnie z powyższymi regułami R1 i R2, ale tego już niestety nie mam...
Byłabym bardzo wdzięczna za pomoc....
Muszę udowodnić następujące tw:
Jeżeli spójny płaski graf G, taki że \(\displaystyle{ \delta (G) \ge 3}\) jest grafem bez 4-cykli, to zachodzi jeden z następujących warunków:
1) istnieje krawędź xy taka, że \(\displaystyle{ deg_{G}x + deg_{G} y \le 7}\)
2)istnieje 4-wierzchołek v , ktory jest incydentny z dwiema nieprzyległymi 3-ścianami \(\displaystyle{ f_{1}=[v v_{1} v_{2}]}\) i \(\displaystyle{ f_{2}=[v v_{3} v_{4}]}\) takimi, że \(\displaystyle{ deg_{G} v_{i} \ge 4}\) dla i=1,2,3,4 oraz w zbiorze \(\displaystyle{ \{v_{1}, v_{2}, v_{3}, v_{4} \}}\) jest co najwyżej jeden wierzchołek stopnia większego niż 4.
Dowód przeprowadzam następująco:
załóżmy, że tw nie jest prawdziwe. Stosując klasyczny wzór Eulera\(\displaystyle{ \left| V(G)\right|-\left| E(G)\right| + \left| F(G)\right| =2}\) oraz lematy o uściskach dłoni dla wierzchołków i ścian otrzymujemy:
\(\displaystyle{ \sum_{v \in V(G)} (2 deg_{G} v -6)+ \sum_{f \in F(G)} (deg_{G} f - 6)= -12.}\)
(nie rozumiem tutaj tych kroków jak z tych lematów i wzoru eulera korzystamy, że powstaje taki wzór...proszę o wytłumaczenie:/)
Dalej niech \(\displaystyle{ w(x)= \begin{cases} 2 deg_{g} x - 6 dla x \in V(G) \\ deg_{g} x - 6 dla x \in F(G)\end{cases}}\) będzie waga wierzchołka x, wtedy możemy zapisać (początkowy wzór) nastepująco: \(\displaystyle{ \sum_{x \in V(G) \cup F(G)} w(x)= -12.}\)
To oznacza, że ogólna suma wag jest liczbą ujemną. Wprowadźmy pewną szczególną wymianę taką, że ogólna suma wag jest niezmieniona, ale funkcja wagowa jest nieujemna dla wszystkich \(\displaystyle{ x \in V(G) \cup F(G)}\). Zatem \(\displaystyle{ 0 \le \sum_{x \in V(G) \cup F(G)} w'(x)= \sum_{x \in V(G) \cup F(G)} w(x)= -12,}\) co jest sprzecznością. (tutaj też byłabym wdzięczna za pomoc, bo nie wiem sjądpóźniej nagle bierze się mi w'(x) ? )
Teraz zdefiniujemy zasady wymiany( których też nie rozumiem....
)R1 : jeżeli \(\displaystyle{ deg_{G} v=4}\), toprzenosimy 1 z v do każdej incydentnej {4,4,4}-ściany w \(\displaystyle{ F_{3}(v)}\), \(\displaystyle{ \frac{3}{4}}\) do każdej incydentnej {4,4,t}-ściany gdzie \(\displaystyle{ t > 4}\)
oraz \(\displaystyle{ \frac{1}{4}}\) do każdej 5-ściany w \(\displaystyle{ F_{5}(v)}\).
R2 : jeżeli \(\displaystyle{ deg_{G} v > 4}\) to przenosimy \(\displaystyle{ \frac{3}{2}}\) z v do każdej 3-ściany w \(\displaystyle{ F_{3}(v)}\), i \(\displaystyle{ \frac{1}{3}}\) do każdej 5-ściany w \(\displaystyle{ F_{5}(v)}\).
Pozostało pokazać, ze funkcja wagi w'(x) jest nieujemna dla każdego \(\displaystyle{ x \in V(G) \cup F(G)}\). Trzeba to wykazać zgodnie z powyższymi regułami R1 i R2, ale tego już niestety nie mam...
Byłabym bardzo wdzięczna za pomoc....