728x90 AdSpace

Theo dõi và chia sẻ các bài viết mới
Tin nhanh

Bài toán girth cho đồ thị Trương Phước Nhân

Mời các bạn xem một bài viết của tác giả Trương Phước Nhân về Bài toán girth cho đồ thị.

Đọc file Bài toán Girth cho đồ thị dạng ảnh
bai toan girth cho do thi truong phuoc nhan

Bài toán girth cho đồ thị phần 2
Đọc File Bài toán girth cho đồ thị dạng Latex
 
Girth của đồ thị $G$ là độ dài nhỏ nhất có thể có của một chu trình chứa trong $G$.
Bài toán 1:
Chứng minh rằng nếu $G$ là một đồ thị đều bậc $k$ với girth bằng 5 thì $G$ chứa tối thiểu là ${{k}^{2}}+1$ đỉnh.
Lời giải :
Với đỉnh $v\in V\left( G \right)$ , ta đặt $N\left( v \right):=\left\{ {{v}_{1}},{{v}_{2}},...,{{v}_{k}} \right\}$ là tập các lân cận của đỉnh $v$. Đầu tiên , với hai lân cận bất kì của đỉnh $v$ sẽ không có cạnh nối giữa chúng ( nếu ngược lại ta sẽ thu được một tam giác , mâu thuẫn giả thiết), có nghĩa là với ${{v}_{i}}$,${{v}_{j}}$phân biệt ta luôn có ${{v}_{i}}\notin N\left( {{v}_{j}} \right)$. 
Tiếp theo ,ta có $\left( N\left( {{v}_{i}} \right)\backslash \left\{ v \right\} \right)\cap \left( N\left( {{v}_{j}} \right)\backslash \left\{ v \right\} \right)=\varnothing $ bởi vì nếu như tồn tại đỉnh $u$ sao cho
$u\in \left( N\left( {{v}_{i}} \right)\backslash \left\{ v \right\} \right)\cap \left( N\left( {{v}_{j}} \right)\backslash \left\{ v \right\} \right)$ thì 4 đỉnh $\left\{ v,{{v}_{i}},u,{{v}_{j}} \right\}$ sẽ tạo thành 4-chu trình, mâu thuẫn với giả thiết.
Từ các phân tích trên ta nhận ra rằng :
        $\left| V\left( G \right) \right|\ge \left| \left\{ v \right\} \right|+\left| N\left( v \right) \right|+\sum\limits_{i=1}^{k}{\left| N\left( {{v}_{i}} \right)\backslash \left\{ v \right\} \right|}=1+k+k\left( k-1 \right)={{k}^{2}}+1$ , đpcm
Bài toán 2:
Hỏi giá  trị của $k$ có thể bằng bao nhiêu để tồn tại một đồ thị đều bậc $k$ với girth bằng 5 với chính xác là ${{k}^{2}}+1$đỉnh ?   
Lời giải: Gọi ma trận liên thuộc tương ứng với đồ thị cần tìm là  $A={{\left( {{a}_{ij}} \right)}_{n\times n}}$ với $n={{k}^{2}}+1$ trong đó ${{a}_{ij}}=1$ khi và chỉ khi hai đỉnh ${{v}_{i}}$ và ${{v}_{j}}$ có cạnh nối với nhau và ${{a}_{ij}}=0$ trong trường hợp ngược lại ( Lưu ý $A$ là một ma trận đối xứng). Ta chuyển bài toán sang ngôn ngữ ma trận . Đầu tiên , ta chứng minh rằng ma trận  $A$ thỏa mãn phương trình sau: ${{A}^{2}}+A-\left( k-1 \right)I=J$, trong đó $I$ là ma trận đơn vị còn $J$ là ma trận với tất cả các phần tử đều bằng 1.
Thật vậy :${{\left( {{A}^{2}} \right)}_{ij}}=\sum\limits_{k=1}^{n}{{{a}_{ik}}{{a}_{kj}}}=$ số các lân cận chung của hai đỉnh ${{v}_{i}}$ và ${{v}_{j}}$
Bây giờ ta xem xét hai đỉnh   và   bất kì của đồ thị:
 1)$i=j$ thì  ${{\left( {{A}^{2}} \right)}_{ij}}=k\Rightarrow {{\left( {{A}^{2}} \right)}_{ij}}+{{\left( A \right)}_{ij}}-\left( k-1 \right)\left( {{I}_{ij}} \right)=k+0-\left( k-1 \right)=1$  
 2)$i\ne j$ và hai đỉnh ${{v}_{i}}$ và ${{v}_{j}}$ có cạnh nối giữa chúng thì ${{v}_{i}}$ và ${{v}_{j}}$ không thể có thêm lân cận chung ( nếu ngược lại ta sẽ thu được một tam giác) nên ${{\left( {{A}^{2}} \right)}_{ij}}=k\Rightarrow {{\left( {{A}^{2}} \right)}_{ij}}+{{\left( A \right)}_{ij}}-\left( k-1 \right)\left( {{I}_{ij}} \right)=k+0-\left( k-1 \right)=1$
 3) $i\ne j$ và hai đỉnh ${{v}_{i}}$ và ${{v}_{j}}$ không có cạnh nối với nhau thì ${{v}_{i}}$ và ${{v}_{j}}$ chỉ có duy nhất một lân cận chung.
 Giả sử phản chứng rằng : ${{v}_{i}}$ và ${{v}_{j}}$ không có lân cận chung. Theo những phân tích của bài toán 1 thì ta bằng cách đặt $N\left( {{v}_{i}} \right):=\left\{ {{x}_{1}},...,{{x}_{k}} \right\}$ thì $V\left( G \right)=\left\{ {{v}_{i}} \right\}\cup N\left( {{v}_{i}} \right)\cup \bigcup\limits_{1\le i\le k}{N\left( {{x}_{i}} \right)}\backslash \left\{ {{v}_{i}} \right\}$ . Do không có cạnh nối với giữa  ${{v}_{i}}$ và ${{v}_{j}}$ nên ${{v}_{j}}\in \bigcup\limits_{1\le i\le k}{N\left( {{x}_{i}} \right)}\backslash \left\{ {{v}_{i}} \right\}\Rightarrow {{v}_{j}}\in N\left( {{x}_{l}} \right)\backslash \left\{ {{v}_{i}} \right\}$ hay nói cách khác ${{x}_{l}}$ là lân cận chung của${{v}_{i}}$ và ${{v}_{j}}$, mâu thuẫn.
Đồng thời ta nhận thấy rằng lân cận chung này là duy nhất vì nếu không ta sẽ thu được 4- chu trình dẫn đến mâu thuẫn nên ${{\left( {{A}^{2}} \right)}_{ij}}=1\Rightarrow {{\left( {{A}^{2}} \right)}_{ij}}+{{\left( A \right)}_{ij}}-\left( k-1 \right)\left( {{I}_{ij}} \right)=1+0-\left( k-1 \right).0=1$
Từ các phân tích trên ta suy ra: ${{A}^{2}}+A-\left( k-1 \right)I=J$ đpcm
Tiếp theo ta tiến hành nghiên cứu phổ của ma trận $A$. Nhận xét , bằng việc tính toán trực tiếp ta nhận thấy: $A1=k1$ với $1$ và vector gồm toàn số 1 nên $k$ là một giá trị riêng với vector riêng tương ứng $1$.
 Do $A$ là một ma trận thực đối xứng nên $A$ có $n$ giá trị riêng và đồng thời ta cũng xác định được một cơ sở trực chuẩn riêng tương ứng với $n$ ( bằng quá trình Hilbert-Schmidt).
         Gọi $\lambda $ là một vector riêng khác $k$ và có vector riêng tương ứng thuộc cơ sở trực chuẩn ta tạm gọi là $e$ nên $\left\langle e,1 \right\rangle =0$ hay $Je=0$

       $\Rightarrow \left( {{A}^{2}}+A-\left( k-1 \right)I \right)e=0$
           $\Rightarrow \left( {{\lambda }^{2}}+\lambda -\left( k-1 \right) \right)e=0$
                $\Rightarrow {{\lambda }^{2}}+\lambda -\left( k-1 \right)=0$
        Giải phương trình bậc hai này ta thu được : $\lambda =\frac{1}{2}\left( -1\pm \sqrt{4k-3} \right)$.
 Đặt ${{\lambda }_{1}}:=\frac{1}{2}\left( -1-\sqrt{4k-3} \right)$ và ${{\lambda }_{2}}:=\frac{1}{2}\left( -1+\sqrt{4k-3} \right)$ nên các giá trị riêng có thể có của $A$ gồm $\left\{ {{\lambda }_{1}},{{\lambda }_{2}},k \right\}$. Gọi $m,{{m}_{1}},{{m}_{2}}$ lần lượt là số bội của các giá trị $k,{{\lambda }_{1}},{{\lambda }_{2}}$ ( các số bội này có thể bằng 0 nếu giá trị tương ứng không phải là giá trị riêng của $A$) nên ${{A}^{2}}+A-\left( k-1 \right)I$ có $m$ giá trị riêng ${{k}^{2}}+k-\left( k-1 \right)={{k}^{2}}+1$;
${{m}_{1}}$ giá trị riêng $\lambda _{1}^{2}+{{\lambda }_{1}}-\left( k-1 \right)=0$ ; ${{m}_{2}}$ giá trị riêng $\lambda _{2}^{2}+{{\lambda }_{2}}-\left( k-1 \right)=0$. Bằng tính toán trực tiếp ta nhận ra rằng ma trận $J$ có 1 giá trị riêng ${{k}^{2}}+1$ và ${{k}^{2}}$ giá trị riêng 0.
Kết hợp với phương trình ma trận ${{A}^{2}}+A-\left( k-1 \right)I=J$ ta suy ra $m=1$ và ${{m}_{1}}+{{m}_{2}}={{k}^{2}}$.
 Từ lý thuyết đại số tuyến tính ta biết rằng vết của một ma trận bằng tổng các giá trị riêng của ma trận và  bằng tổng các giá trị trên đường chéo chính của ma trận đó và, ta có hệ thức sau:
                                                      $k+{{m}_{1}}{{\lambda }_{1}}+{{m}_{2}}{{\lambda }_{2}}=0$
Thay các giá trị ${{\lambda }_{1}}=\frac{1}{2}\left( -1-\sqrt{4k-3} \right)$ và ${{\lambda }_{2}}=\frac{1}{2}\left( -1+\sqrt{4k-3} \right)$ vào hệ thức trên và thu gọn ta được :
                                           $2k-{{k}^{2}}+\left( {{m}_{1}}-{{m}_{2}} \right)\sqrt{4k-3}=0$
1)Nếu ${{m}_{1}}={{m}_{2}}$ thì $k=2$
2)Nếu ${{m}_{1}}\ne {{m}_{2}}$ thì $\sqrt{4k-3}$ là một số hữu tỉ nên nó là một số nguyên ( chứng minh đơn giản nên ta không trình bày ), ta tạm gọi là $s$. Khi đó : $k=\frac{{{s}^{2}}+3}{4}$ . Thay biểu thức $2k-{{k}^{2}}+\left( {{m}_{1}}-{{m}_{2}} \right)\sqrt{4k-3}=0$ và tiến hành thu gọn ta thu được kết quả : $\left[ {{s}^{3}}-2s-16\left( {{m}_{1}}-{{m}_{2}} \right) \right]s=15$ .
Từ đây ta suy ra $s$ là một ước số của 15 nên $s\in \left\{ 1,3,5,15 \right\}$. Lưu ý rằng với $s=1$ ta tính được $k=1$  và hiển nhiên là không thể có đồ thị với girth 5 trong trường hợp này. Với $s=3,5,15$ ta tính được $k=3,7,57$.
Vậy các giá trị có thể có của $k$ là $\left\{ 2,3,7,57 \right\}$.
Tài liệu tham khảo:
[1]. Các bài giảng trên internet
[2]. Martin Aigner, Gunter M. Ziegler, Proofs from THE BOOK, Third Edition. 
[3]. Martin Erickson, Aha! Solution, First Edition.     

Lấy về máy tài liệu Bài toán girth cho đồ thị: Download
Bài toán girth cho đồ thị Trương Phước Nhân Reviewed by Tân Phúc on 04:41:00 Rating: 5 Mời các bạn xem một bài viết của tác giả Trương Phước Nhân về Bài toán girth cho đồ thị. Liên quan: Định lý Dilworth và ứng dụng Trương P...

Không có nhận xét nào:

Xin vui lòng để lại vài dòng nhận xét hoặc đánh giá có nội dung. Sự quan tâm, chia sẻ của quý độc giả sẽ tạo ra những trải nghiệm tuyệt vời cho cộng đồng bạn đọc cả nước.