text:
Đồ thị hai phía
Trong Lý thuyết đồ thị, đồ thị hai phía (đồ thị lưỡng phân hay đồ thị hai phần) (tiếng Anh: bipartite graph) là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.
Những tính chất của đồ thị hai phía được đề cập đến đầu tiên bởi Dénes Kőnig(1916) [1][2][3]. Dénes Kőnig cũng là người viết cuốn sách đầu tiên Theorie der endlichen und unendlichen Graphen 1936 [4] về Lý thuyết đồ thị.
Đồ thị hai phía xuất hiện trong các bài toán dùng đồ thị biểu diễn quan hệ hai ngôi giữa hai tập A và tập B không giao nhau. Một ví dụ cho quan hệ này là quan hệ hôn nhân giữa hai tập hợp người nam và nữ.
Mục lục
Định nghĩa[sửa | sửa mã nguồn]
Một đồ thị đơn vô hướng được gọi là hai phía mà tập đỉnh của nó có thể chia thành hai tập con và rời nhau sao cho bất kì cạnh nào của đồ thị cũng nối một đỉnh của với một đỉnh thuộc . Khi đó người ta còn kí hiệu là: và gọi một tập (chẳng hạn ) là tập các đỉnh trái và tập còn lại (chẳng hạn ) là tập các đỉnh phải của đồ thị hai phía ..[5]
Nếu thì được gọi là đồ thị hai phía cân bằng.
Ví dụ[sửa | sửa mã nguồn]
không phải là đồ thị lưỡng phân vì nếu ta chia các đỉnh của nó thành 2 phần rời nhau thì một trong 2 phần này phải chứa 2 đỉnh. Nếu đồ thị là lưỡng phân thì các đỉnh này không thể nối với nhau bằng một cạnh. Nhưng trong K3 mỗi đỉnh được nối với đỉnh khác bằng một cạnh.
Một vài ví dụ trừu tượng:
- Mỗi cây là đồ thị hai phía.[6]
- Biểu đồ chu kỳ với một số chẵn các đỉnh là đồ thị hai phía.[6]
- Biểu đồ Hypercube, các hình khối từng phần, và đồ thị trung bình là đồ thị hai phía.[7]
Thuật toán kiểm tra một đồ thị liên thông là đồ thị hai phía[5][sửa | sửa mã nguồn]
Để kiểm tra một đồ thị liên thông có phải là đồ thị hai phía hay không, ta có thể áp dụng thuật toán sau:
Với một đỉnh bất kì:
X:= {v}; Y:=; repeat Y:= Y Kề(X); X:= X Kề(Y); until (X Y ) or (X và Y là tối đại - không bổ sung được nữa); if X Y then (Không phải đồ thị hai phía) else (Đây là đồ thị hai phía X là tập các đỉnh trái: các đỉnh đến được từ v qua một số chẵn cạnh Y là tập các đỉnh cạnh phải: các đỉnh đến được từ v qua một số lẻ cạnh);
Định lí[sửa | sửa mã nguồn]
Một đồ thị G là hai phần khi và chỉ khi G không có chu trình lẻ[2].
- Chứng minh
Chứng minh theo chiều thuận
G là hai phần và có 1 chu trình đi qua u ∈ U khi đó số lần đi vào u bằng số lần đi ra khỏi u và tổng số cạnh của chu trình là số cạnh kề với tập đỉnh thuộc một trong hai tập U hoặc V thuộc chu trình đó,nên ta có 1 chu trình độ dài chẵn.
Ta có hình vẽ minh hoạ như sau:
Chứng minh theo chiều nghịch
Không mất tính tổng quát ta giả sử G liên thông,chọn một đỉnh u bất kì,với mỗi đỉnh v ∈ V(G) do tính liên thông của G sẽ tồn tại một đường đi từ u đến v nếu độ dài đường đi này là chẵn thì cho v vào tập U,ngược lại thì cho v vào V.
Ta sẽ chứng minh:
1. Cách xây dựng này là không mâu thuẫn.
2. Không có cạnh nào trong U.
3. Không có cạnh nào trong V.
Từ ba điều trên thì đồ thị đã cho là đồ thị hai phần.
Ta đi chứng minh 3 ý trên.
1. Giả sử phản chứng tồn tại hai đường đi chẵn,lẻ từ u đến v thì sẽ tồn tại một chu trình lẻ suy ra mâu thuẫn với giả thiết.
2. Giả sử tồn tại cạnh (x,y) ∈ U khi đó tồn tại đường đi độ dài chẵn từ u đến x và từ v đến y nên sẽ có 1 chu trình lẻ.
3. Tương tự như trường hợp 2.
Định lí được chứng minh
Tính chất[sửa | sửa mã nguồn]
- Kích thước của phủ đỉnh nhỏ nhất bằng kích thước của cặp ghép lớn nhất
- Kích thước của tập độc lập lớn nhất cộng kích thước của cặp ghép lớn nhất bằng số đỉnh.
- Trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất bằng kích thước tập độc lập lớn nhất
- Trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất cộng kích thước của phủ đỉnh nhỏ nhất bằng số đỉnh.
- Một đồ thị là hai phía khi và chỉ khi có thể tô màu nó bằng hai màu.[8]
- Quang phổ của một đồ thị là đối xứng khi và chỉ khi nó là một đồ thị hai phía.[9]
Ứng dụng[sửa | sửa mã nguồn]
- Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp (matching problem), quan hệ hôn nhân giữa tập những người đàn ông và tập những người đàn bà, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v...[5]
- Một ví dụ bài toán phân công công việc. Giả sử ta có một nhóm người P và một tập công việc J, trong đó không phải ai cũng hợp với mọi công việc. Ta có thể mô hình bài toán bằng một đồ thị với tập đỉnh là P + J. Nếu người có thể làm công việc , đồ thị sẽ có một cạnh nối giữa và . Định lý hôn nhân cung cấp một đặc điểm của đồ thị hai phía: tồn tại cặp ghép hoàn hảo (perfect matching).
- Đồ thị hai phía được sử dụng trong lý thuyết mã hóa (coding theory) hiện đại, đặc biệt khi giải mã các codeword nhận được từ kênh. Đồ thị nhân tử (factor graph) và đồ thị Tanner là các ví dụ.[10]
- Đồ thị Levi là một dạng của đồ thị hai phía sử dụng để mô hình tỷ lệ mắc giữa điểm và đường trong một cấu hình.[11]
Xem thêm[sửa | sửa mã nguồn]
Liên kết ngoài[sửa | sửa mã nguồn]
Tham khảo[sửa | sửa mã nguồn]
- ^ Asratian, Armen S., Tristan MJ Denley, and Roland Häggkvist. Bipartite graphs and their applications. Vol. 131. Cambridge University Press, 1998.
- ^ a ă D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), no. 4, 453–465.
- ^ Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig.
- ^ Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen, Leipzig: Akademische Verlagsgesellschaft. Translated from German by Richard McCoart, Theory of finite and infinite graphs, Birkhäuser, 1990, ISBN 0-8176-3389-8
- ^ a ă â Giải thuật và lập trình (Lê Minh Hoàng), Đại Học Sư Phạm Hà Nội, 1999-2002
- ^ a ă Scheinerman, Edward A. (2012), Mathematics: A Discrete Introduction (ấn bản 3), Cengage Learning, tr. 363, ISBN 9780840049421.
- ^ Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.
- ^ Asratian, Denley & Häggkvist (1998), p. 7.
- ^ Biggs, Norman (1994), Algebraic Graph Theory, Cambridge Mathematical Library (ấn bản 2), Cambridge University Press, tr. 53, ISBN 9780521458979.
- ^ Moon, Todd K. (2005), Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, tr. 638, ISBN 9780471648000.
- ^ Grünbaum, Branko (2009), Configurations of Points and Lines, Graduate Studies in Mathematics 103, American Mathematical Society, tr. 28, ISBN 9780821843086.
- The Art of Computer Programming, 3rd edition, Author: Donald E.Knuth. Publisher: Addison-Wesley, 1998
- Introduction to Algorithms, 2nd edition, ISBN: 0262032937, Author: Thomas H.Cormen, Charles E.Leiserson, Ronald,L.Rivest. Publisher: The MIT Press,2001
- Lí thuyết đồ thị (Trần Đan Thư - Dương Anh Đức), Trường Đại Học Khoa Học Tự Nhiên, Nhà Xuất Bản Đại học Quốc gia TP Hồ Chí Minh - 2008
- Giải thuật và lập trình (Lê Minh Hoàng), Đại Học Sư Phạm Hà Nội, 1999-2002

markdown:
# Đồ thị hai phía
Trong
[Lý thuyết đồ thị](/wiki/L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B), **đồ thị hai phía** ( **đồ thị lưỡng phân** hay **đồ thị hai phần**) (tiếng Anh: [bipartite graph](/w/index.php?title=Bipartite_graph&action=edit&redlink=1)) là một [đồ thị](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_(to%C3%A1n_h%E1%BB%8Dc)) đặc biệt, trong đó [tập](/wiki/T%E1%BA%ADp_h%E1%BB%A3p) các [đỉnh](/wiki/%C4%90%E1%BB%89nh_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)) có thể được chia thành hai [tập không giao nhau](/w/index.php?title=T%E1%BA%ADp_kh%C3%B4ng_giao_nhau&action=edit&redlink=1) thỏa mãn điều kiện không có [cạnh](/wiki/C%E1%BA%A1nh_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)) nối hai đỉnh bất kỳ thuộc cùng một tập.
Những tính chất của đồ thị hai phía được đề cập đến đầu tiên bởi
[Dénes Kőnig](/w/index.php?title=D%C3%A9nes_K%C5%91nig&action=edit&redlink=1)(1916) [[1]](#cite_note-1) [[2]](#cite_note-s2-2) . [3] [Dénes Kőnig](/w/index.php?title=D%C3%A9nes_K%C5%91nig&action=edit&redlink=1)cũng là người viết cuốn sách đầu tiên [Theorie der endlichen und unendlichen Graphen](/w/index.php?title=Theorie_der_endlichen_und_unendlichen_Graphen&action=edit&redlink=1)1936 về Lý thuyết đồ thị. [[4]](#cite_note-4)
Đồ thị hai phía xuất hiện trong các bài toán dùng đồ thị biểu diễn quan hệ hai ngôi giữa hai tập A và tập B không giao nhau. Một ví dụ cho quan hệ này là quan hệ hôn nhân giữa hai tập hợp người nam và nữ.
## Mục lục
## Định nghĩa[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=1)]
Một
[đồ thị đơn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%C6%A1n&action=edit&redlink=1) [vô hướng](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_v%C3%B4_h%C6%B0%E1%BB%9Bng)
được gọi là
**hai phía** mà tập đỉnh của nó có thể chia thành hai tập con
và
rời nhau sao cho bất kì cạnh nào của đồ thị cũng nối một đỉnh của
với một đỉnh thuộc
. Khi đó người ta còn kí hiệu là:
và gọi một tập (chẳng hạn
) là
**tập các đỉnh trái** và tập còn lại (chẳng hạn
) là
**tập các đỉnh phải** của đồ thị hai phía
..
[[5]](#cite_note-lmh-5)
Nếu
thì
được gọi là đồ thị hai phía
**cân bằng**.
## Ví dụ[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=2)]
không phải là đồ thị lưỡng phân vì nếu ta chia các đỉnh của nó thành 2 phần rời nhau thì một trong 2 phần này phải chứa 2 đỉnh. Nếu đồ thị là lưỡng phân thì các đỉnh này không thể nối với nhau bằng một cạnh. Nhưng trong K3 mỗi đỉnh được nối với đỉnh khác bằng một cạnh.
Một vài ví dụ trừu tượng:
- Mỗi cây là đồ thị hai phía.
[[6]](#cite_note-s12-6) [Biểu đồ chu kỳ](/w/index.php?title=Bi%E1%BB%83u_%C4%91%E1%BB%93_chu_k%E1%BB%B3&action=edit&redlink=1)với một số chẵn các đỉnh là đồ thị hai phía. [[6]](#cite_note-s12-6) [Biểu đồ Hypercube](/w/index.php?title=Bi%E1%BB%83u_%C4%91%E1%BB%93_Hypercube&action=edit&redlink=1), các hình khối từng phần, và đồ thị trung bình là đồ thị hai phía. [[7]](#cite_note-7)
## Thuật toán kiểm tra một đồ thị liên thông là đồ thị hai phía
[ [[5]](#cite_note-lmh-5) [sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=3)] [[5]](#cite_note-lmh-5)
Để kiểm tra một đồ thị liên thông có phải là đồ thị hai phía hay không, ta có thể áp dụng thuật toán sau:
Với một đỉnh
bất kì:
X:= {v}; Y:=
; repeat Y:= Y
Kề(X); X:= X
Kề(Y); until (X
Y
) or (X và Y là tối đại - không bổ sung được nữa); if X
Y
then (Không phải đồ thị hai phía) else (Đây là đồ thị hai phía X là tập các đỉnh trái: các đỉnh đến được từ v qua một số chẵn cạnh Y là tập các đỉnh cạnh phải: các đỉnh đến được từ v qua một số lẻ cạnh);
## Định lí[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=4)]
Một đồ thị G là hai phần khi và chỉ khi G không có chu trình lẻ
. [2] **Chứng minh** **Chứng minh theo chiều thuận**
G là hai phần và có 1 chu trình đi qua u ∈ U khi đó số lần đi vào u bằng số lần đi ra khỏi u và tổng số cạnh của chu trình là số cạnh kề với tập đỉnh thuộc một trong hai tập U hoặc V thuộc chu trình đó,nên ta có 1 chu trình độ dài chẵn.
Ta có hình vẽ minh hoạ như sau:
**Chứng minh theo chiều nghịch**
Không mất tính tổng quát ta giả sử G liên thông,chọn một đỉnh u bất kì,với mỗi đỉnh v ∈ V(G) do tính liên thông của G sẽ tồn tại một đường đi từ u đến v nếu độ dài đường đi này là chẵn thì cho v vào tập U,ngược lại thì cho v vào V.
Ta sẽ chứng minh:
1. Cách xây dựng này là không mâu thuẫn.
2. Không có cạnh nào trong U.
3. Không có cạnh nào trong V.
Từ ba điều trên thì đồ thị đã cho là đồ thị hai phần.
**Ta đi chứng minh 3 ý trên.**
1. Giả sử phản chứng tồn tại hai đường đi chẵn,lẻ từ u đến v thì sẽ tồn tại một chu trình lẻ suy ra mâu thuẫn với giả thiết.
2. Giả sử tồn tại cạnh (x,y) ∈ U khi đó tồn tại đường đi độ dài chẵn từ u đến x và từ v đến y nên sẽ có 1 chu trình lẻ.
3. Tương tự như trường hợp 2.
**Định lí được chứng minh**
## Tính chất[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=5)]
- Kích thước của
[phủ đỉnh nhỏ nhất](/w/index.php?title=Ph%E1%BB%A7_%C4%91%E1%BB%89nh_nh%E1%BB%8F_nh%E1%BA%A5t&action=edit&redlink=1)bằng kích thước của [cặp ghép lớn nhất](/w/index.php?title=C%E1%BA%B7p_gh%C3%A9p_l%E1%BB%9Bn_nh%E1%BA%A5t&action=edit&redlink=1)
- Kích thước của
[tập độc lập lớn nhất](/w/index.php?title=T%E1%BA%ADp_%C4%91%E1%BB%99c_l%E1%BA%ADp_l%E1%BB%9Bn_nh%E1%BA%A5t&action=edit&redlink=1)cộng kích thước của [cặp ghép lớn nhất](/w/index.php?title=C%E1%BA%B7p_gh%C3%A9p_l%E1%BB%9Bn_nh%E1%BA%A5t&action=edit&redlink=1)bằng số đỉnh.
- Trong đồ thị hai phía
[liên thông](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_li%C3%AAn_th%C3%B4ng), kích thước của [phủ cạnh nhỏ nhất](/w/index.php?title=Ph%E1%BB%A7_c%E1%BA%A1nh_nh%E1%BB%8F_nh%E1%BA%A5t&action=edit&redlink=1)bằng kích thước [tập độc lập lớn nhất](/w/index.php?title=T%E1%BA%ADp_%C4%91%E1%BB%99c_l%E1%BA%ADp_l%E1%BB%9Bn_nh%E1%BA%A5t&action=edit&redlink=1)
- Trong đồ thị hai phía
[liên thông](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_li%C3%AAn_th%C3%B4ng), kích thước của [phủ cạnh nhỏ nhất](/w/index.php?title=Ph%E1%BB%A7_c%E1%BA%A1nh_nh%E1%BB%8F_nh%E1%BA%A5t&action=edit&redlink=1)cộng kích thước của [phủ đỉnh nhỏ nhất](/w/index.php?title=Ph%E1%BB%A7_%C4%91%E1%BB%89nh_nh%E1%BB%8F_nh%E1%BA%A5t&action=edit&redlink=1)bằng số đỉnh.
- Một đồ thị là hai phía khi và chỉ khi có thể tô màu nó bằng hai màu.
[[8]](#cite_note-adh98-7-8)
- Quang phổ của một đồ thị là đối xứng khi và chỉ khi nó là một đồ thị hai phía.
[[9]](#cite_note-9)
## Ứng dụng[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=6)]
- Đồ thị hai phía thường được dùng để mô hình các
[bài toán ghép cặp](/w/index.php?title=B%C3%A0i_to%C3%A1n_gh%C3%A9p_c%E1%BA%B7p&action=edit&redlink=1)( *matching problem*), quan hệ hôn nhân giữa tập những người đàn ông và tập những người đàn bà, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v... [[5]](#cite_note-lmh-5)
- Một ví dụ bài toán phân công công việc. Giả sử ta có một nhóm người
*P*và một tập công việc *J*, trong đó không phải ai cũng hợp với mọi công việc. Ta có thể mô hình bài toán bằng một đồ thị với tập đỉnh là *P*+ *J*. Nếu người
có thể làm công việc
, đồ thị sẽ có một cạnh nối giữa
và
.
[Định lý hôn nhân](/w/index.php?title=%C4%90%E1%BB%8Bnh_l%C3%BD_h%C3%B4n_nh%C3%A2n&action=edit&redlink=1)cung cấp một đặc điểm của đồ thị hai phía: tồn tại [cặp ghép hoàn hảo](/w/index.php?title=C%E1%BA%B7p_gh%C3%A9p_ho%C3%A0n_h%E1%BA%A3o&action=edit&redlink=1)( *perfect matching*).
- Đồ thị hai phía được sử dụng trong
[lý thuyết mã hóa](/wiki/L%C3%BD_thuy%E1%BA%BFt_m%C3%A3_h%C3%B3a)( *coding theory*) hiện đại, đặc biệt khi giải mã các codeword nhận được từ kênh. [Đồ thị nhân tử](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_nh%C3%A2n_t%E1%BB%AD&action=edit&redlink=1)( *factor graph*) và [đồ thị Tanner](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_Tanner&action=edit&redlink=1)là các ví dụ. [[10]](#cite_note-10)
- Đồ thị
[Levi](/w/index.php?title=Levi&action=edit&redlink=1)là một dạng của đồ thị hai phía sử dụng để mô hình tỷ lệ mắc giữa điểm và đường trong một cấu hình. [[11]](#cite_note-11)
## Xem thêm[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=7) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=7)]
|
|![]()
[Đồ thị hai phía](//commons.wikimedia.org/wiki/Category:Bipartite_graphs?uselang=vi)
## Liên kết ngoài[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=8) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=8)]
## Tham khảo[
[sửa](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&veaction=edit&vesection=9) | [sửa mã nguồn](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa&action=edit§ion=9)] **Asratian, Armen S., Tristan MJ Denley, and Roland Häggkvist. Bipartite graphs and their applications. Vol. 131. Cambridge University Press, 1998.** [^](#cite_ref-1)
- ^
**a** [D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), no. 4, 453–465.](#cite_ref-s2_2-1) **ă** [^](#cite_ref-3) [Asratian, Denley & Häggkvist (1998)](#CITEREFAsratianDenleyH.C3.A4ggkvist1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by [Dénes Kőnig](/w/index.php?title=D%C3%A9nes_K%C5%91nig&action=edit&redlink=1). **Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen, Leipzig: Akademische Verlagsgesellschaft. Translated from German by Richard McCoart, Theory of finite and infinite graphs, Birkhäuser, 1990,** [^](#cite_ref-4) [ISBN 0-8176-3389-8](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0817633898)
- ^
**a** **ă** [Giải thuật và lập trình (Lê Minh Hoàng),](#cite_ref-lmh_5-2) **â** [Đại Học Sư Phạm Hà Nội](/w/index.php?title=%C4%90%E1%BA%A1i_H%E1%BB%8Dc_S%C6%B0_Ph%E1%BA%A1m_H%C3%A0_N%E1%BB%99i&action=edit&redlink=1), 1999-2002
- ^
**a** [Scheinerman, Edward A. (2012),](#cite_ref-s12_6-1) **ă** [(ấn bản 3), Cengage Learning, tr. 363,](http://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363) *Mathematics: A Discrete Introduction* [ISBN](/wiki/ISBN) [9780840049421](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/9780840049421). **Ovchinnikov, Sergei (2011),** [^](#cite_ref-7) *Graphs and Cubes*, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181. [^](#cite_ref-adh98-7_8-0) [Asratian, Denley & Häggkvist (1998)](#CITEREFAsratianDenleyH.C3.A4ggkvist1998), p. 7. **Biggs, Norman (1994),** [^](#cite_ref-9) [, Cambridge Mathematical Library (ấn bản 2), Cambridge University Press, tr. 53,](http://books.google.com/books?id=6TasRmIFOxQC&pg=PA53) *Algebraic Graph Theory* [ISBN](/wiki/ISBN) [9780521458979](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/9780521458979). **Moon, Todd K. (2005),** [^](#cite_ref-10) [, John Wiley & Sons, tr. 638,](http://books.google.com/books?id=adxb8CRx5vQC&pg=PA638) *Error Correction Coding: Mathematical Methods and Algorithms* [ISBN](/wiki/ISBN) [9780471648000](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/9780471648000). [^](#cite_ref-11) [Grünbaum, Branko](/w/index.php?title=Branko_Gr%C3%BCnbaum&action=edit&redlink=1)(2009), [, Graduate Studies in Mathematics](http://books.google.com/books?id=mRw571GNa5UC&pg=PA28) *Configurations of Points and Lines* **103**, [American Mathematical Society](/w/index.php?title=American_Mathematical_Society&action=edit&redlink=1), tr. 28, [ISBN](/wiki/ISBN) [9780821843086](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/9780821843086). [The Art of Computer Programming](/wiki/The_Art_of_Computer_Programming), 3rd edition, Author: Donald E.Knuth. Publisher: Addison-Wesley, 1998 [Introduction to Algorithms](/w/index.php?title=Introduction_to_Algorithms&action=edit&redlink=1), 2nd edition, [ISBN](/wiki/ISBN): [0262032937](/w/index.php?title=0262032937&action=edit&redlink=1), Author: Thomas H.Cormen, Charles E.Leiserson, Ronald,L.Rivest. Publisher: The MIT Press,2001
- Lí thuyết đồ thị (Trần Đan Thư - Dương Anh Đức),
[Trường Đại Học Khoa Học Tự Nhiên](/w/index.php?title=Tr%C6%B0%E1%BB%9Dng_%C4%90%E1%BA%A1i_H%E1%BB%8Dc_Khoa_H%E1%BB%8Dc_T%E1%BB%B1_Nhi%C3%AAn&action=edit&redlink=1), Nhà Xuất Bản Đại học Quốc gia TP Hồ Chí Minh - 2008
- Giải thuật và lập trình (Lê Minh Hoàng),
[Đại Học Sư Phạm Hà Nội](/w/index.php?title=%C4%90%E1%BA%A1i_H%E1%BB%8Dc_S%C6%B0_Ph%E1%BA%A1m_H%C3%A0_N%E1%BB%99i&action=edit&redlink=1), 1999-2002

X-Content-Type-Options: nosniff

Content-language: vi

X-UA-Compatible: IE=Edge

Vary: Accept-Encoding,Cookie

Via: 1.1 varnish, 1.1 varnish

Accept-Ranges: bytes

X-Cache: cp1067 miss (0), cp1054 frontend miss (0)

Cache-Control: private, s-maxage=0, max-age=0, must-revalidate

Set-Cookie: WMF-Last-Access=24-May-2015;Path=/;HttpOnly;Expires=Thu, 25 Jun 2015 00:00:00 GMT


text:
Bổ đề Farkas
Bổ đề Farkas là một kết quả toán học phát biểu như sau: một vectơ hoặc nằm trong một nón lồi hoặc tồn tại một siêu phẳng sao cho vectơ nằm ở một phía của siêu phẳng và nón lồi nằm ở phía kia. Nó được chứng minh đầu tiên bởi nhà toán học người Hungary Gyula Farkas Bản mẫu:Harvs. Nó có nhiều ứng dụng, chẳng hạn như trong chứng minh của định lý Karush–Kuhn–Tucker trong quy hoạch phi tuyến.
Phát biểu bổ đề[sửa | sửa mã nguồn]
Giả sử A là một ma trận m × n và b là một vectơ m chiều. Đúng một trong hai trường hợp sau xảy ra:
- Tồn tại vectơ x ∈ Rn sao cho Ax = b và x ≥ 0.
- Tồn tại y ∈ Rm sao cho ATy ≥ 0 và bTy < 0.
Ở đây kí hiệu x ≥ 0 có nghĩa là mọi tọa độ của x đều không âm.
Có nhiều phát biểu tương đương của bổ đề này. Phiên bản trên là của Gale, Kuhn & Tucker (1951).
Ý nghĩa hình học[sửa | sửa mã nguồn]
Đặt a1, …, an ∈ Rm là các cột của A. Bổ đề Farkas khẳng định rằng một trong hai mệnh đề sau là đúng:
- Tồn tại các hệ số x1, …, xn ∈ R, x1, …, xn ≥ 0, sao cho b = x1a1 + ··· + xnan.
- Tồn tại vectơ y ∈ Rm sao cho ai · y ≥ 0 với i = 1, …, n và b · y < 0.
Các vectơ x1a1 + ··· + xnan với hệ số không âm tạo thành một nón lồi sinh bởi tập hợp {a1, …, an} nên mệnh đề thứ nhất nghĩa là b nằm trong hình nón này.
Theo mệnh đề thứ hai, tồn tại y sao cho góc giữa y và các vectơ ai là không quá 90° trong khi góc giữa y và vectơ b là lớn hơn 90°. So với siêu phẳng vuông góc với y, ai nằm ở một phía và vectơ b nằm ở phía kia. Do đó siêu phẳng này chia cắt nón lồi sinh bởi tập hợp {a1, …, an} và vectơ b.
Để minh họa, xét n,m=2 và a1 = (1,0)T và a2 = (1,1)T. Nón lồi sinh bởi a1 và a2 là một góc nhọn trong góc phần tư thứ nhất của mặt phẳng Oxy. Giả sử b = (0,1). Khi đó, b không nằm trong nón lồi a1x1+a2x2. Do đó, tồn tại siêu phẳng chia cắt chúng. Đặt y = (1,−1)T. Ta nhận thấy a1 · y = 1, a2 · y = 0, và b · y = −1. Do đó siêu phẳng với vectơ pháp tuyến y chia cắt nón lồi a1x1+a2x2 và b.
Do đó có thể diễn đạt bổ đề Farkas dưới dạng hình học như sau: cho một nón lồi và một vectơ, hoặc vectơ nằm trong nón lồi hoặc tồn tại một siêu phẳng chia cắt vectơ và nón lồi, nhưng không thể cả hai.
Biến thể[sửa | sửa mã nguồn]
Có nhiều biến thể của bổ đề Farkas như định lý Gordan: hoặc có nghiệm x, hoặc có nghiệm khác không y với y ≥ 0.
Một phiên bản dễ nhớ là như sau: nếu một hệ bất phương trình không có nghiệm thì tồn tại một chứng minh phản chứng dưới dạng một tổ hợp tuyến tính với các hệ số không âm. Dưới dạng công thức: nếu ≤ vô nghiệm thì , , ≥ có nghiệm[1]. (ghi chú là một tổ hợp tuyến tính của vế trái, là tổ hợp tuyến tính tương ứng của vế phải các bất phương trình. Do tổ hợp tuyến tính không âm tạo ra vectơ không ở vế trái và −1 ở vế phải, hệ bất phương trình rõ ràng vô nghiệm)
Tài liệu tham khảo[sửa | sửa mã nguồn]
- Berkovitz, Leonard D. (2001), Convexity and Optimization in , New York: John Wiley & Sons, ISBN 978-0-471-35281-5.
- Farkas, Gyula (1894), “A Fourier-féle mechanikai elv alkamazásai”, Mathematikai és Természettudományi Értesítő 12: 457–472, “reference from Schrijver's Combinatorial Optimization textbook”.
- Farkas, Julius (Gyula) (1902), “Über die Theorie der Einfachen Ungleichungen”, Journal für die Reine und Angewandte Mathematik 124 (124): 1–27, doi:10.1515/crll.1902.124.1.
- Rockafellar, R. T. (1979), Convex Analysis, Princeton University Press, tr. 200
- Gale; Kuhn; Tucker (1951), “Linear Programming and the Theory of Games - Chapter XII”, trong Koopmans, Activity Analysis of Production and Allocation, Wiley. Xem bổ đề 1 ở trang 318.
- Kutateladze, S. (2010), “The Farkas Lemma Revisited”, Siberian Mathematical Journal 51 (1): 78–87, doi:10.1007/s11202-010-0010-y.
Ghi chú[sửa | sửa mã nguồn]
- ^ Boyd, Stephen P.; Vandenberghe, Lieven (2004), “Phần 5.8.3” (pdf), Convex Optimization, Cambridge University Press, ISBN 9780521833783, truy cập 15 tháng 10, 2011

markdown:
# Bổ đề Farkas
**Bổ đề Farkas** là một kết quả [toán học](/wiki/To%C3%A1n_h%E1%BB%8Dc) phát biểu như sau: một vectơ hoặc nằm trong một [nón lồi](/w/index.php?title=N%C3%B3n_l%E1%BB%93i(%C4%91%E1%BA%A1i_s%E1%BB%91_tuy%E1%BA%BFn_t%C3%ADnh)&action=edit&redlink=1) hoặc tồn tại một [siêu phẳng](/wiki/Si%C3%AAu_ph%E1%BA%B3ng) sao cho vectơ nằm ở một phía của siêu phẳng và nón lồi nằm ở phía kia. Nó được chứng minh đầu tiên bởi nhà toán học người Hungary [Gyula Farkas](/w/index.php?title=Gyula_Farkas&action=edit&redlink=1) [Bản mẫu:Harvs](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:Harvs&action=edit&redlink=1). Nó có nhiều ứng dụng, chẳng hạn như trong chứng minh của [định lý Karush–Kuhn–Tucker](/w/index.php?title=%C4%90i%E1%BB%81u_ki%E1%BB%87n_Karush-Kuhn-Tucker&action=edit&redlink=1) trong [quy hoạch phi tuyến](/w/index.php?title=Quy_ho%E1%BA%A1ch_phi_tuy%E1%BA%BFn&action=edit&redlink=1).
## Phát biểu bổ đề[
[sửa](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&action=edit§ion=1)]
Giả sử
*A* là một [ma trận](/wiki/Ma_tr%E1%BA%ADn_(to%C3%A1n_h%E1%BB%8Dc)) *m* × *n* và *b* là một [vectơ](/wiki/Vect%C6%A1) *m* chiều. Đúng một trong hai trường hợp sau xảy ra:
- Tồn tại vectơ
*x*∈ **R** sao cho *n* *Ax*= *b*và *x*≥ 0.
- Tồn tại
*y*∈ **R** sao cho *m* *A*≥ 0 và Ty *b*< 0. Ty
Ở đây kí hiệu
*x* ≥ 0 có nghĩa là mọi tọa độ của *x* đều không âm.
Có nhiều phát biểu tương đương của bổ đề này. Phiên bản trên là của
[Gale, Kuhn & Tucker (1951)](#CITEREFGaleKuhnTucker1951).
## Ý nghĩa hình học[
[sửa](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&action=edit§ion=2)]
Đặt
*a* 1, …, *a* ∈ n **R** là các cột của *m* *A*. Bổ đề Farkas khẳng định rằng một trong hai mệnh đề sau là đúng:
- Tồn tại các hệ số
*x* 1, …, *x* ∈ *n* **R**, *x* 1, …, *x* ≥ 0, sao cho *n* *b*= *x* 1 *a* 1+ ··· + *x* *n* *a* . *n*
- Tồn tại vectơ
*y*∈ **R** sao cho *m* *a* · *i* *y*≥ 0 với *i*= 1, …, *n*và *b*· *y*< 0.
Các vectơ
*x* 1 *a* 1 + ··· + *x* *n* *a* với hệ số không âm tạo thành một n [nón lồi](/wiki/N%C3%B3n_l%E1%BB%93i)sinh bởi tập hợp { *a* 1, …, *a* } nên mệnh đề thứ nhất nghĩa là *n* *b*nằm trong hình nón này.
Theo mệnh đề thứ hai, tồn tại
*y* sao cho góc giữa *y* và các vectơ *a* là không quá 90° trong khi góc giữa i *y*và vectơ *b*là lớn hơn 90°. So với siêu phẳng vuông góc với *y*, *a* nằm ở một phía và vectơ *i* *b*nằm ở phía kia. Do đó siêu phẳng này chia cắt nón lồi sinh bởi tập hợp { *a* 1, …, *a* } và vectơ *n* *b*.
Để minh họa, xét
*n,m*=2 và *a* 1 = (1,0) T và *a* 2 = (1,1) T. Nón lồi sinh bởi *a* 1 và *a* 2 là một góc nhọn trong góc phần tư thứ nhất của mặt phẳng *Oxy*. Giả sử *b* = (0,1). Khi đó, *b* không nằm trong nón lồi *a* 1 *x* 1+ *a* 2 *x* 2. Do đó, tồn tại siêu phẳng chia cắt chúng. Đặt *y* = (1,−1) T. Ta nhận thấy *a* 1 · *y* = 1, *a* 2 · *y* = 0, và *b* · *y* = −1. Do đó siêu phẳng với vectơ pháp tuyến *y* chia cắt nón lồi *a* 1 *x* 1+ *a* 2 *x* 2 và *b*.
Do đó có thể diễn đạt bổ đề Farkas dưới dạng hình học như sau: cho một nón lồi và một vectơ, hoặc vectơ nằm trong nón lồi hoặc tồn tại một siêu phẳng chia cắt vectơ và nón lồi, nhưng không thể cả hai.
## Biến thể[
[sửa](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&action=edit§ion=3)]
Có nhiều biến thể của bổ đề Farkas như
[định lý Gordan](/w/index.php?title=%C4%90%E1%BB%8Bnh_l%C3%BD_Gordan&action=edit&redlink=1): hoặc
có nghiệm
*x*, hoặc
có nghiệm khác không
*y* với *y* ≥ 0.
Một phiên bản dễ nhớ là như sau: nếu một hệ bất phương trình không có nghiệm thì tồn tại một chứng minh phản chứng dưới dạng một tổ hợp tuyến tính với các hệ số không âm. Dưới dạng công thức: nếu
≤
vô nghiệm thì
,
,
≥
có nghiệm
. (ghi chú [1] ![ y^T A](http://upload.wikimedia.org/math/c/2/f/c2f3646dc9fde1cf91164dcbaf1af676.png)
![ y^T b](http://upload.wikimedia.org/math/a/1/6/a160d24974a28223ba28184bd57f5a6d.png)
## Tài liệu tham khảo[
[sửa](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&action=edit§ion=4)]
- Berkovitz, Leonard D. (2001),
*Convexity and Optimization in*, New York: [John Wiley & Sons](/w/index.php?title=John_Wiley_%26_Sons&action=edit&redlink=1), [ISBN](/wiki/ISBN) [978-0-471-35281-5](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/978-0-471-35281-5). [Farkas, Gyula](/w/index.php?title=Gyula_Farkas_(natural_scientist)&action=edit&redlink=1)(1894), “A Fourier-féle mechanikai elv alkamazásai”, *Mathematikai és Természettudományi Értesítő* **12**: 457–472, “reference from Schrijver's Combinatorial Optimization textbook”. [Farkas, Julius (Gyula)](/w/index.php?title=Gyula_Farkas_(natural_scientist)&action=edit&redlink=1)(1902), [“Über die Theorie der Einfachen Ungleichungen”](http://gdz.sub.uni-goettingen.de/en/dms/load/img/?PPN=PPN243919689_0124&DMDID=dmdlog4), *Journal für die Reine und Angewandte Mathematik* **124**(124): 1–27, [doi](/wiki/DOI): [10.1515/crll.1902.124.1](http://dx.doi.org/10.1515%2Fcrll.1902.124.1). [Rockafellar, R. T.](/w/index.php?title=R._T._Rockafellar&action=edit&redlink=1)(1979), *Convex Analysis*, Princeton University Press, tr. 200
- Gale; Kuhn; Tucker (1951),
[“Linear Programming and the Theory of Games - Chapter XII”](http://cowles.econ.yale.edu/P/cm/m13/m13-19.pdf), trong Koopmans, *Activity Analysis of Production and Allocation*, Wiley. Xem bổ đề 1 ở trang 318.
- Kutateladze, S. (2010),
[“The Farkas Lemma Revisited”](http://www.math.nsc.ru/LBRT/g2/english/ssk/preprint229.pdf), *Siberian Mathematical Journal* **51**(1): 78–87, [doi](/wiki/DOI): [10.1007/s11202-010-0010-y](http://dx.doi.org/10.1007%2Fs11202-010-0010-y).
## Ghi chú[
[sửa](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=B%E1%BB%95_%C4%91%E1%BB%81_Farkas&action=edit§ion=5)] **Boyd, Stephen P.; Vandenberghe, Lieven (2004),** [^](#cite_ref-1) [“Phần 5.8.3”](http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)(pdf), *Convex Optimization*, Cambridge University Press, [ISBN](/wiki/ISBN) [9780521833783](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/9780521833783), truy cập 15 tháng 10, 2011

WARC-Type: response

Content-Type: application/http; msgtype=response

Content-Type: text/html; charset=UTF-8

Connection: close

Content-Encoding: gzip

X-Cache: cp1053 miss (0), cp1054 frontend miss (0)


text:
kingklip
Từ điển mở Wiktionary
Bước tới:
dẫn lái
,
tìm
Tiếng Anh
[
sửa
]
Danh từ
[
sửa
]
kingklip
Loại
lương
biển
ăn được.
Tham khảo
[
sửa
]
Hồ Ngọc Đức,
Dự án Từ điển tiếng Việt miễn phí
(
chi tiết
)
Lấy từ “
http://vi.wiktionary.org/w/index.php?title=kingklip&oldid=1104902
”
Thể loại
:
Mục từ tiếng Anh
Danh từ
Danh từ tiếng Anh
Trình đơn chuyển hướng
Công cụ cá nhân
Mở tài khoản
Đăng nhập
Không gian tên
Mục từ
Thảo luận
Biến thể
Các hiển thị
Tra
Sửa đổi
Xem lịch sử
Khác
Tìm kiếm
Chuyển hướng
Trang Chính
Cộng đồng
Thay đổi gần đây
Mục từ ngẫu nhiên
Trợ giúp
Thảo luận chung
Quyên góp
Chỉ mục
Ngôn ngữ
Chữ cái
Bộ thủ
Từ loại
Chuyên ngành
In/xuất ra
Tạo một quyển sách
Tải về dưới dạng PDF
Bản in được
Công cụ
Các liên kết đến đây
Thay đổi liên quan
Tải tập tin lên
Các trang đặc biệt
Liên kết thường trực
Thông tin trang
Trích dẫn trang này
Ngôn ngữ định nghĩa
English
தமிழ்
Trang này được sửa đổi lần cuối lúc 11:53 ngày 12 tháng 6 năm 2010.
Văn bản được phát hành theo
Giấy phép Creative Commons Ghi công–Chia sẻ tương tự
; có thể áp dụng điều khoản bổ sung. Xem
Điều khoản Sử dụng
để biết thêm chi tiết.
Quy định quyền riêng tư
Giới thiệu Wiktionary
Lời phủ nhận
Nhà phát triển
Phiên bản di động

X-Cache: cp1068 miss (0), cp1066 frontend miss (0)


text:
Giày TOM đang là xu hướng hè 2012. Chất liệu vải bố thân thiện với môi trường cùng sự tiện dụng khiến giày TOM thu hút được sự quan tâm của rất nhìu sao HOLLYWOOD.
Ngoài giày TOM đã đáp ứng nhu cầu đông đảo của KH,Đặc biệt là trong mùa hè này thật phù hợp với các bạn trẻ.nhanh tay chon cho mình đôi giày thật phù hợp ... chỉ có 210k/ 1 đôi...
alo mình nhé 0949233660
chi tiết vào web: http:// shopwen.net
vanle1006Giày TOM đang là xu hướng hè 2012. Chất liệu vải bố thân thiện với môi trường cùng sự tiện dụng khiến giày TOM thu hút được sự quan tâm của rất nhìu sao HOLLYWOOD.
Ngoài giày TOM đã đáp ứng nhu cầu đông đảo của KH,Đặc biệt là trong mùa hè này thật phù hợp với các bạn trẻ.nhanh tay chon cho mình đôi giày thật phù hợp ... chỉ có 190k/ 1 đôi...
Đến đc sau đây xem hàng: 24/25, đường số 2, F16, Q gò vấp nhé các bạn..... hoăc alo mình 0949233660
dễ thương woa'....

markdown:
Giày TOM đang là xu hướng hè 2012. Chất liệu vải bố thân thiện với môi trường cùng sự tiện dụng khiến giày TOM thu hút được sự quan tâm của rất nhìu sao HOLLYWOOD.
Ngoài giày TOM đã đáp ứng nhu cầu đông đảo của KH,Đặc biệt là trong mùa hè này thật phù hợp với các bạn trẻ.nhanh tay chon cho mình đôi giày thật phù hợp ... chỉ có 210k/ 1 đôi...
alo mình nhé 0949233660
chi tiết vào web: http:// shopwen.net
|
|
|
|
UP 4766990 HOT gửi 8500
|
|
|
|5GIAY 0 gửi 8700
vanle1006
Giày TOM đang là xu hướng hè 2012. Chất liệu vải bố thân thiện với môi trường cùng sự tiện dụng khiến giày TOM thu hút được sự quan tâm của rất nhìu sao HOLLYWOOD.
Ngoài giày TOM đã đáp ứng nhu cầu đông đảo của KH,Đặc biệt là trong mùa hè này thật phù hợp với các bạn trẻ.nhanh tay chon cho mình đôi giày thật phù hợp ... chỉ có 190k/ 1 đôi...
Đến đc sau đây xem hàng: 24/25, đường số 2, F16, Q gò vấp nhé các bạn
..... hoăc alo mình 0949233660
dễ thương woa'....
|
|

WARC-Truncated: length

Vary: Accept-Encoding,User-Agent

Set-Cookie: vbseo_loggedin=deleted; expires=Sat, 24-May-2014 09:22:02 GMT; path=/

Cache-Control: private

Pragma: private

Server: Nhat Nguyet Websphere 12.3 build 3.456.234.2600

X-Powered-By: nhatnguyet-MISS


text: Máy tính của mình vẫn vào wifi ngon lành mà mấy bữa nay tự dưng ko vào wifi đc nữa,mặc dù máy vẫn nhận wifi xung quanh nhưng mạng wifi mình vẫn xài bữa nay ko vào đc,cột wifi có dấu x màu đỏ..trong khi đó thì điện thoại của mình vẫn vào mạng wifi bình thường.Khi minh click vào mạng đó thì nó hiện dòng chữ " the setting saved on this computer for the network do not match the requirements of the network".Mình ko rành về máy tính..hic..ai biết giúp dùm mình với..

markdown:
# Cột sóng wifi có dấu x đỏ..Giúp mình với
Thảo luận trong '
[[Win] Hỏi đáp - CSKN](forums/win-hoi-dap-cskn.201/)' bắt đầu bởi [mezmez](members/mezmez.375737/), [20/3/12](threads/cot-song-wifi-co-dau-x-do-giup-minh-voi.1154831/).
Trả lời: 45, Xem: 138428.
Trang 1 / 3
Thảo luận trong '
[[Win] Hỏi đáp - CSKN](forums/win-hoi-dap-cskn.201/)' bắt đầu bởi [mezmez](members/mezmez.375737/), [20/3/12](threads/cot-song-wifi-co-dau-x-do-giup-minh-voi.1154831/).
Trả lời: 45, Xem: 138428.

Server: LiteSpeed

Vary: User-Agent

Cache-control: private, max-age=0

Set-Cookie: xf_session=715d4017f5d8ebded2ad292fff1c5a90; path=/; secure; httponly

X-Frame-Options: SAMEORIGIN