markdown:
# Tô màu đồ thị
Trong
[Lý thuyết đồ thị](/wiki/L%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B), **tô màu đồ thị** (tiếng Anh: *graph coloring*) là trường hợp đặc biệt của [gán nhãn đồ thị](/w/index.php?title=G%C3%A1n_nh%C3%A3n_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit&redlink=1), mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị có thể là: **tô màu đỉnh**(tiếng Anh: *vertex coloring*) là gán cho mỗi đỉnh của đồ thị một màu nào đó sao cho không có hai đỉnh nào [liền kề](/w/index.php?title=Li%E1%BB%81n_k%E1%BB%81&action=edit&redlink=1)lại trùng màu nhau; **tô màu cạnh**(tiếng Anh: *edge coloring*) là gán cho mỗi cạnh của đồ thị một màu nào đó sao cho sao cho không có 2 cạnh nào trùng màu; **tô màu miền**(tiếng Anh: *face coloring*) là gán cho mỗi miền của [đồ thị phẳng](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_ph%E1%BA%B3ng)một màu sao cho không có 2 miền có chung đường biên lại cùng màu. **Sắc số** (tiếng Anh: *chromatic number*) của một đồ thị là số màu ít nhất để tô các đỉnh. Sắc số của đồ thị *G* được kí hiệu là χ( *G*). **Số màu cạnh** (tiếng Anh: *chromatic index*) của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị *G* được kí hiệu là χ'( *G*).
Số màu cạnh của đồ thị
*G* bất kì bằng sắc số của [đồ thị đường](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%C6%B0%E1%BB%9Dng&action=edit&redlink=1) L( *(G)*) của đồ thị đó:
- χ'(
*G*) = χ(L( *G*)),
do đó việc nghiên cứu tô màu cạnh của
*G* tương đương với nghiên cứu tô màu đỉnh của L( *G*).
## Mục lục
[1 Các định lí và tính chất](#C.C3.A1c_.C4.91.E1.BB.8Bnh_l.C3.AD_v.C3.A0_t.C3.ADnh_ch.E1.BA.A5t) [2 Sắc số và số màu cạnh của một số đồ thị cơ bản](#S.E1.BA.AFc_s.E1.BB.91_v.C3.A0_s.E1.BB.91_m.C3.A0u_c.E1.BA.A1nh_c.E1.BB.A7a_m.E1.BB.99t_s.E1.BB.91_.C4.91.E1.BB.93_th.E1.BB.8B_c.C6.A1_b.E1.BA.A3n) [3 Ứng dụng](#.E1.BB.A8ng_d.E1.BB.A5ng) [4 Xem thêm](#Xem_th.C3.AAm) [5 Chú thích](#Ch.C3.BA_th.C3.ADch) [6 Tham khảo](#Tham_kh.E1.BA.A3o) [7 Liên kết ngoài](#Li.C3.AAn_k.E1.BA.BFt_ngo.C3.A0i)
## Các định lí và tính chất[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=1)]
### Các giá trị giới hạn của sắc số[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=2)]
Rõ ràng sắc số của một đồ thị sẽ không vượt quá số đỉnh của nó (bậc của đồ thị):
.
Nếu
*G* có [clique](/wiki/Clique) kích thước *k* thì cần ít nhất *k* màu để tô màu đỉnh cho clique này (xem thêm bài về [đồ thị đầy đủ](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7)), như vậy sắc số của một đồ thị sẽ không nhỏ hơn *chỉ số clique* của đồ thị đó:
Nếu đồ thị đơn
*G* có bậc cực đại bằng Δ(G) thì sắc số của nó không vượt quá Δ(G)+1 . [1]
- Gọi số đỉnh của
*G*là *n*.
- Ta dùng Δ(G)+1 màu để tô
*n*đỉnh của *G*như sau: xuất phát từ đỉnh thứ nhất đến đỉnh thứ *n*, tô màu đỉnh đầu tiên bằng 1 màu tùy ý trong Δ(G)+1 màu. Tô màu đỉnh kế tiếp bằng một màu khác với các màu đã tô cho các láng giềng của đỉnh đó. Việc tô màu này luôn thực hiện được, đến lượt 1 đỉnh bất kì, ta luôn có màu để tô cho nó, vì số màu Δ(G)+1 lớn hơn bậc của đỉnh bất kì.
Tổng quát hơn là định lý Brook, định lý khẳng định rằng:
*Tất cả mọi đồ thị đơn và liên thông G, ngoại trừ* [đồ thị đầy đủ](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7)
và
[đồ thị chu trình](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_chu_tr%C3%ACnh)bậc lẻ
, đều có sắc số nhỏ hơn hoặc bằng bậc cực đại:
Δ(G).
-
Nếu đồ thị
*G* có *m* cạnh thì sắc số của nó thỏa mãn:
- Chứng minh quy nạp theo
*m*( *m*là số tự nhiên) mệnh đề (*) sau: *nếu đồ thị G có không quá m cạnh thì sắc số của nó thỏa mãn:*
-
- Với
*m*=0,1, mệnh đề (*) đúng.
- Giả sử mệnh đề (*) đúng đến
*m*-1. Xét *m*.
- Gọi
là số tự nhiên lớn nhất thỏa mãn:
- Nếu bậc cực đại của
*G*nhỏ hơn
thì như ta đã biết, sắc số của
*G*không vượt quá bậc cực đại của nó cộng với một, nên sẽ không vượt quá
, suy ra luôn điều phải chứng minh.
- Nếu bậc cực đại của
*G*lớn hơn hoặc bằng
, suy ra trong
*G*tồn tại đỉnh *a*có deg( *a*) lớn hơn hoặc bằng
.
- Xóa đỉnh
*a*và các cạnh liên thuộc của nó khỏi *G*ta nhận được đồ thị mới là G', đồ thị này có số cạnh thỏa mãn:
- Theo giả thiết quy nạp, mệnh đề (*) đúng cho m' nên:
,
-
- Suy ra:
.
-
- Tức là sắc số của G' không thể vượt quá
, từ đó suy ra sắc số của
*G*không vượt quá
. Như vậy mệnh đề cũng đúng với
*m*.
- Suy ra mệnh đề (*) đúng với mọi
*m*là số tự nhiên.
### Một số định lý liên quan của sắc số[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=3)]
#### Định lý 1[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=4)]
Bất cứ chu trình độ dài lẻ nào cũng đều có sắc số bằng 3
**Chứng minh:** Giả sử chu trình có độ dài là
ta chứng minh theo số
chu trình gồm 3 đỉnh mà 2 đỉnh bất kì đều kề nhau
dùng đúng 3 màu để tô
Giả sử
là một chu trình có độ dài
với các dãy đỉnh là
,
,...,
,
,
.
Nối
với
ta được một chu trình
'có độ dài
.
Theo giả thuyết quy nạp chu trình
' có sắc số bằng 3.
Lấy màu của
tô cho
còn màu của
tô cho
.
Chu trình
được tô màu mà không thêm màu mới vào.
Vậy chu trình
có sắc số bằng 3
#### Định lý 2[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=5)]
Đồ thị đầy đủ n đỉnh K
n có sắc số bằng n
Một số tiêu chuẩn đơn giản để kiểm tra xem 1 đồ thị có hai sắc số hay không:
**Ta có định lý:**Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G có hai sắc số khi và chỉ khi G không có chu trình đơn vô hướng độ dài lẻ. **Chứng minh:**
- Giả sử G là đồ thị có hai sắc số. Theo
*Định lý 1*thì G không thể có chu trình đơn vô hướng độ dài lẻ.
- Ngược lại giả sử G không có chu trình đơn vô hướng độ dài lẻ. Không mất tính tổng quát có thể xem G liên thông.
Chọn 1 đỉnh a nào đó bất kì trong đồ thị
Đặt
(m: số màu)
Với
Ta ký hiệu
là độ dài đường đi vô hướng ngắn nhất nối
với
Đặt
mod 2
*Ta sẽ chứng minh m là hàm màu của G*
Giả sử
kề nhau
- Lấy
là đường đi vô hướng ngắn nhất nối a với x có độ dài
là đường đi vô hướng ngắn nhất nối
với
có độ dài
Chu trình đơn
có độ dài
phải là một số chẵn
Vậy thì
là một số lẻ
khác nhau tính chẵn lẻ
Hàm tô màu m có hai giá trị, vậy sắc số ≤ 2. G có ít nhất một cạnh nên sắc số của nó bằng 2
Từ định lý trên ta có hệ quả sau: Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.
#### Định lý 3[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=6)] **Phát biểu:** Nếu G có chứa 1 đồ thị con đẳng cấu với K n thì
.
**Chứng minh:** Hiển nhiên
### Các giá trị giới hạn của số màu cạnh[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=7) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=7)]
#### Định lí 1[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=8) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=8)] *Số màu cạnh của đồ thị đơn*G *bất kì không vượt quá số đỉnh của nó*.
Xét đồ thị
có hai đỉnh bất kì liền kề và
có các khuyên.
*n* là số đỉnh của
.
Đánh số các đỉnh của
là
.
Chỉ cần chứng minh
có thể tô màu các cạnh bởi
*n* màu thì suy ra đồ thị đơn *G* bất kì có số đỉnh không vượt quá *n* đều có thể tô các cạnh bởi *n* màu.
Kí hiệu các màu là
.
Khi đó ta có cách tô màu cho
như sau.
Ma trận dưới đây biểu thị cách tô màu, trong đó:
- giá trị ở hàng thứ
*i*cột *j*chính là màu được gán cho cạnh
;
** khẳng định rằng đối với Định lý König** [đồ thị hai phía](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa) *G*, số màu cạnh của nó bằng bậc cực đại của nó: ![ \chi'(G) = \Delta(G)](http://upload.wikimedia.org/math/9/6/c/96c47bd66173e28bc2584e9b881dc42a.png)
** khẳng định rằng, nếu đồ thị đơn Định lý Vizing** *G*có bậc cực đại bằng ![ \Delta(G)](http://upload.wikimedia.org/math/a/4/f/a4f724421f6ac2231112e5157ed96417.png)
![ \Delta(G)](http://upload.wikimedia.org/math/a/4/f/a4f724421f6ac2231112e5157ed96417.png)
![ \Delta(G)+1](http://upload.wikimedia.org/math/9/1/0/9102ba713b6a94be1844a19974256134.png)
### Đa thức màu[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=9) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=9)]
Xem bài
[đa thức màu](/wiki/%C4%90a_th%E1%BB%A9c_m%C3%A0u).
## Sắc số và số màu cạnh của một số đồ thị cơ bản[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=10) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=10)]
Khái niệm sắc số liên quan đến bài toán tô màu như sau: Hãy tô màu các đỉnh của đồ thị đã cho, sao cho 2 đỉnh kề phải được tô bằng hai màu khác nhau
### Đồ thị hai phía[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=11) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=11)] [Đồ thị hai phía](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_hai_ph%C3%ADa) đầy đủ
có sắc số bằng 2: χ(
)=2. Mở rộng: một đồ thị hai phía bất kì có sắc số không vượt quá 2.
Ví dụ minh họa là các đỉnh của đồ thị
có thể được tô bởi hai màu xanh và đỏ.
### Đồ thị chu trình[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=12) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=12)] [Đồ thị chu trình](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_chu_tr%C3%ACnh)
có sắc số bằng:
- χ(
)= 3, nếu n lẻ.
- χ(
)= 2, nếu n chẵn.
Số màu cạnh:
- χ'(
)= 3, nếu n lẻ.
- χ'(
)= 2, nếu n chẵn.
### Đồ thị bánh xe[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=13) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=13)] [Đồ thị bánh xe](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_b%C3%A1nh_xe)
(
*n*≥4) có sắc số bằng:
- χ(
)= 4, nếu
*n*chẵn;
- χ(
)= 3, nếu
*n*lẻ.
Số màu cạnh (
*n*≥3):
- χ'(
)=
*n*-1.
### Đồ thị đầy đủ[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=14) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=14)]
-
[Đồ thị đầy đủ](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7)7 đỉnh có sắc số bằng 7.
-
-
[Đồ thị đầy đủ](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_%C4%91%E1%BA%A7y_%C4%91%E1%BB%A7)
có sắc số bằng:
- χ(
) =
*n*.
Số màu cạnh:
- χ'(
) =
*n*, nếu *n*lẻ.
- χ'(
) =
*n*-1, nếu *n*chẵn.
Đánh số các đỉnh của
là
.
Do mỗi đỉnh của
có bậc bằng
*n*-1, nên số màu cạnh của nó không nhỏ hơn *n*-1, do đó χ'(
) bằng
*n* hoặc *n*-1. **Chứng minh χ'()= n-1 với n chẵn:**
- Ta chỉ cần chỉ ra cách tô
*n*-1 màu cho các cạnh của
là được.
- Kí hiệu các màu là
.
- Ma trận dưới đây biểu thị cách tô màu, trong đó:
- giá trị ở hàng thứ
*i*cột *j*chính là màu được gán cho cạnh
;
- X nghĩa là không được gán màu.
- giá trị ở hàng thứ
- Ví dụ với
*n*=6, ta có cách tô màu như sau: **Chứng minh χ'()= n với n lẻ:**
- Trái lại, giả sử tồn tại
*n*lẻ sao cho χ'(
) =
*n*-1.
- Xét màu
*M*bất kì, các cạnh tô màu *M*kí hiệu là
, trong đó
là các đầu mút đôi một phân biệt. Như vậy có 2
*k*đỉnh có cạnh liên thuộc tô bởi màu *M*, mà *n*lẻ nên tồn tại ít nhất một đỉnh
nào đó không có cạnh liên thuộc tô bởi màu
*M*. Như vậy các cạnh liên thuộc với đỉnh
chỉ được tô bởi không quá
*n*-2 màu, mà
(vô lí).
### Đồ thị siêu khối[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=15) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=15)] [Đồ thị siêu khối](/w/index.php?title=%C4%90%E1%BB%93_th%E1%BB%8B_si%C3%AAu_kh%E1%BB%91i&action=edit&redlink=1)
có sắc số bằng 2, vì bản thân nó là đồ thị phân đôi.
## Ứng dụng[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=16) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=16)]
### Tô màu bản đồ[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=17) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=17)]
Trên các
[bản đồ](/wiki/B%E1%BA%A3n_%C4%91%E1%BB%93), các miền khác nhau (miền ở đây được hiểu là các quốc gia trên bản đồ thế giới hay các tỉnh trong một bản đồ hành chính quốc gia) được tô màu sao cho 2 miền có chung biên giới không trùng màu nhau. Đối với bản đồ có nhiều miền, nếu ta dùng một số lượng lớn màu thì sẽ rất khó phân biệt các miền có màu gần giống nhau, vì thế người ta chỉ dùng một số lượng màu nhất định để tô màu bản đồ. Một bài toán được đặt ra là: có thể dùng ít nhất bao nhiêu màu để tô màu một bản đồ sao cho các miền kề nhau không cùng một màu (tr.593). [2]
Bài toán này dẫn đến
[định lý bốn màu](/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_b%E1%BB%91n_m%C3%A0u) nổi tiếng và [định lý năm màu](/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_n%C4%83m_m%C3%A0u) . Các dạng bài toán tô màu bản đồ có thể áp dụng [3] [Thuật toán tô màu Greedy](/wiki/Thu%E1%BA%ADt_to%C3%A1n_t%C3%B4_m%C3%A0u_Greedy)để tìm ra số màu ít nhất để tô cho các miền trên bản đồ.
## Xem thêm[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=18) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=18)]
## Chú thích[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=19) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=19)]
## Tham khảo[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=20) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=20)]
- Barenboim, L.; Elkin, M. (2009), “Distributed (Δ + 1)-coloring in linear (in Δ) time”,
*Proceedings of the 41st*, tr. 111–120, [Symposium on Theory of Computing](/w/index.php?title=Symposium_on_Theory_of_Computing&action=edit&redlink=1) [doi](/wiki/DOI): [10.1145/1536414.1536432](http://dx.doi.org/10.1145%2F1536414.1536432), [ISBN](/wiki/ISBN) [978-1-60558-506-2](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/978-1-60558-506-2)
- Panconesi, A.; Srinivasan, A. (1996), “On the complexity of distributed network decomposition”,
*Journal of Algorithms* **20**
- Schneider, J. (2010),
[“A new technique for distributed symmetry breaking”](http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf), *Proceedings of the* [Symposium on Principles of Distributed Computing](/w/index.php?title=Symposium_on_Principles_of_Distributed_Computing&action=edit&redlink=1)
- Schneider, J. (2008),
[“A log-star distributed maximal independent set algorithm for growth-bounded graphs”](http://www.dcg.ethz.ch/publications/podc08SW.pdf), *Proceedings of the* [Symposium on Principles of Distributed Computing](/w/index.php?title=Symposium_on_Principles_of_Distributed_Computing&action=edit&redlink=1)
- Beigel, R.;
[Eppstein, D.](/w/index.php?title=David_Eppstein&action=edit&redlink=1)(2005), “3-coloring in time O(1.3289 n)”, [Journal of Algorithms](/w/index.php?title=Journal_of_Algorithms&action=edit&redlink=1) **54**(2)): 168–204, [doi](/wiki/DOI): [10.1016/j.jalgor.2004.06.008](http://dx.doi.org/10.1016%2Fj.jalgor.2004.06.008)
- Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), “Set partitioning via inclusion–exclusion”,
[SIAM Journal on Computing](/w/index.php?title=SIAM_Journal_on_Computing&action=edit&redlink=1) **39**(2): 546–563, [doi](/wiki/DOI): [10.1137/070683933](http://dx.doi.org/10.1137%2F070683933)
- Brèlaz, D. (1979), “New methods to color the vertices of a graph”,
[Communications of the ACM](/w/index.php?title=Communications_of_the_ACM&action=edit&redlink=1) **22**(4): 251–256, [doi](/wiki/DOI): [10.1145/359094.359101](http://dx.doi.org/10.1145%2F359094.359101)
- Brooks, R. L.; Tutte, W. T. (1941), “On colouring the nodes of a network”,
[Proceedings of the Cambridge Philosophical Society](/w/index.php?title=Proceedings_of_the_Cambridge_Philosophical_Society&action=edit&redlink=1) **37**(2): 194–197, [doi](/wiki/DOI): [10.1017/S030500410002168X](http://dx.doi.org/10.1017%2FS030500410002168X) [de Bruijn, N. G.](/w/index.php?title=Nicolaas_Govert_de_Bruijn&action=edit&redlink=1); [Erdős, P.](/wiki/Paul_Erd%C5%91s)(1951), [“A colour problem for infinite graphs and a problem in the theory of relations”](http://www.math-inst.hu/~p_erdos/1951-01.pdf), *Nederl. Akad. Wetensch. Proc. Ser. A* **54**: 371–373 (= *Indag. Math.* **13**)
- Byskov, J.M. (2004), “Enumerating maximal independent sets with applications to graph colouring”,
[Operations Research Letters](/w/index.php?title=Operations_Research_Letters&action=edit&redlink=1) **32**(6): 547–556, [doi](/wiki/DOI): [10.1016/j.orl.2004.03.002](http://dx.doi.org/10.1016%2Fj.orl.2004.03.002)
- Chaitin, G. J. (1982), “Register allocation & spilling via graph colouring”,
*Proc. 1982*, tr. 98–105, [SIGPLAN Symposium on Compiler Construction](/w/index.php?title=SIGPLAN_Symposium_on_Compiler_Construction&action=edit&redlink=1) [doi](/wiki/DOI): [10.1145/800230.806984](http://dx.doi.org/10.1145%2F800230.806984), [ISBN](/wiki/ISBN) [0-89791-074-5](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-89791-074-5)
- Cole, R.; Vishkin, U. (1986), “Deterministic coin tossing with applications to optimal parallel list ranking”,
[Information and Control](/w/index.php?title=Information_and_Control&action=edit&redlink=1) **70**(1): 32–53, [doi](/wiki/DOI): [10.1016/S0019-9958(86)80023-7](http://dx.doi.org/10.1016%2FS0019-9958%2886%2980023-7)
- Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990),
*(ấn bản 1), The MIT Press* [Introduction to Algorithms](/w/index.php?title=Introduction_to_Algorithms&action=edit&redlink=1)
- Dailey, D. P. (1980), “Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”,
[Discrete Mathematics](/w/index.php?title=Discrete_Mathematics_(journal)&action=edit&redlink=1) **30**(3): 289–293, [doi](/wiki/DOI): [10.1016/0012-365X(80)90236-8](http://dx.doi.org/10.1016%2F0012-365X%2880%2990236-8)
- Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008),
[“Complexity analysis of a decentralised graph colouring algorithm”](http://www.hamilton.ie/ken_duffy/Downloads/cfl.pdf), *Information Processing Letters* **107**(2): 60–63, [doi](/wiki/DOI): [10.1016/j.ipl.2008.01.002](http://dx.doi.org/10.1016%2Fj.ipl.2008.01.002)
- Fawcett, B. W. (1978), “On infinite full colourings of graphs”,
[Can. J. Math.](/w/index.php?title=Canadian_Journal_of_Mathematics&action=edit&redlink=1) **XXX**: 455–457 [Garey, M. R.](/w/index.php?title=Michael_R._Garey&action=edit&redlink=1); [Johnson, D. S.](/w/index.php?title=David_S._Johnson&action=edit&redlink=1)(1979), *, W.H. Freeman,* [Computers and Intractability: A Guide to the Theory of NP-Completeness](/w/index.php?title=Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness&action=edit&redlink=1) [ISBN](/wiki/ISBN) [0-7167-1045-5](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-7167-1045-5) [Garey, M. R.](/w/index.php?title=Michael_R._Garey&action=edit&redlink=1); [Johnson, D. S.](/w/index.php?title=David_S._Johnson&action=edit&redlink=1); [Stockmeyer, L.](/w/index.php?title=Larry_Stockmeyer&action=edit&redlink=1)(1974), [“Some simplified NP-complete problems”](http://portal.acm.org/citation.cfm?id=803884), *Proceedings of the Sixth Annual ACM Symposium on Theory of Computing*, tr. 47–63, [doi](/wiki/DOI): [10.1145/800119.803884](http://dx.doi.org/10.1145%2F800119.803884)
- Goldberg, L. A.;
[Jerrum, M.](/w/index.php?title=Mark_Jerrum&action=edit&redlink=1)(tháng 7 năm 2008), “Inapproximability of the Tutte polynomial”, [Information and Computation](/w/index.php?title=Information_and_Computation&action=edit&redlink=1) **206**(7): 908–929, [doi](/wiki/DOI): [10.1016/j.ic.2008.04.003](http://dx.doi.org/10.1016%2Fj.ic.2008.04.003)
- Goldberg, A. V.; Plotkin, S. A.; Shannon, G. E. (1988), “Parallel symmetry-breaking in sparse graphs”,
[SIAM Journal on Discrete Mathematics](/w/index.php?title=SIAM_Journal_on_Discrete_Mathematics&action=edit&redlink=1) **1**(4): 434–446, [doi](/wiki/DOI): [10.1137/0401044](http://dx.doi.org/10.1137%2F0401044)
- Guruswami, V.; Khanna, S. (2000), “On the hardness of 4-coloring a 3-colorable graph”,
*Proceedings of the 15th Annual IEEE Conference on Computational Complexity*, tr. 188–197, [doi](/wiki/DOI): [10.1109/CCC.2000.856749](http://dx.doi.org/10.1109%2FCCC.2000.856749), [ISBN](/wiki/ISBN) [0-7695-0674-7](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-7695-0674-7)
- Halldórsson, M. M. (1993), “A still better performance guarantee for approximate graph coloring”,
*Information Processing Letters* **45**: 19–23, [doi](/wiki/DOI): [10.1016/0020-0190(93)90246-6](http://dx.doi.org/10.1016%2F0020-0190%2893%2990246-6)
- Holyer, I. (1981), “The NP-completeness of edge-coloring”,
[SIAM Journal on Computing](/w/index.php?title=SIAM_Journal_on_Computing&action=edit&redlink=1) **10**(4): 718–720, [doi](/wiki/DOI): [10.1137/0210055](http://dx.doi.org/10.1137%2F0210055)
- Crescenzi, P.; Kann, V. (tháng 12 năm 1998), “How to find the best approximation results — a follow-up to Garey and Johnson”,
[ACM SIGACT News](/w/index.php?title=ACM_SIGACT_News&action=edit&redlink=1) **29**(4): 90, [doi](/wiki/DOI): [10.1145/306198.306210](http://dx.doi.org/10.1145%2F306198.306210)
- Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), “On the computational complexity of the Jones and Tutte polynomials”,
[Mathematical Proceedings of the Cambridge Philosophical Society](/w/index.php?title=Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society&action=edit&redlink=1) **108**: 35–53, [doi](/wiki/DOI): [10.1017/S0305004100068936](http://dx.doi.org/10.1017%2FS0305004100068936)
- Jensen, T. R.; Toft, B. (1995),
*Graph Coloring Problems*, Wiley-Interscience, New York, [ISBN](/wiki/ISBN) [0-471-02865-7](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-471-02865-7) [Khot, S.](/w/index.php?title=Subhash_Khot&action=edit&redlink=1)(2001), “Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring”, *Proc. 42nd Annual*, tr. 600–609, [Symposium on Foundations of Computer Science](/w/index.php?title=Symposium_on_Foundations_of_Computer_Science&action=edit&redlink=1) [doi](/wiki/DOI): [10.1109/SFCS.2001.959936](http://dx.doi.org/10.1109%2FSFCS.2001.959936), [ISBN](/wiki/ISBN) [0-7695-1116-3](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-7695-1116-3)
- Kubale, M. (2004),
*Graph Colorings*, American Mathematical Society, [ISBN](/wiki/ISBN) [0-8218-3458-4](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-8218-3458-4)
- Kuhn, F. (2009), “Weak graph colorings: distributed algorithms and applications”,
*Proceedings of the 21st*, tr. 138–144, [Symposium on Parallelism in Algorithms and Architectures](/w/index.php?title=Symposium_on_Parallelism_in_Algorithms_and_Architectures&action=edit&redlink=1) [doi](/wiki/DOI): [10.1145/1583991.1584032](http://dx.doi.org/10.1145%2F1583991.1584032), [ISBN](/wiki/ISBN) [978-1-60558-606-9](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/978-1-60558-606-9) [Lawler, E.L.](/w/index.php?title=Eugene_Lawler&action=edit&redlink=1)(1976), “A note on the complexity of the chromatic number problem”, [Information Processing Letters](/w/index.php?title=Information_Processing_Letters&action=edit&redlink=1) **5**(3): 66–67, [doi](/wiki/DOI): [10.1016/0020-0190(76)90065-X](http://dx.doi.org/10.1016%2F0020-0190%2876%2990065-X)
- Leith, D.J.; Clifford, P. (2006),
[“A Self-Managed Distributed Channel Selection Algorithm for WLAN”](http://www.hamilton.ie/peterc/downloads/rawnet06.pdf), *Proc. RAWNET 2006, Boston, MA* [Linial, N.](/w/index.php?title=Nati_Linial&action=edit&redlink=1)(1992), “Locality in distributed graph algorithms”, [SIAM Journal on Computing](/w/index.php?title=SIAM_Journal_on_Computing&action=edit&redlink=1) **21**(1): 193–201, [doi](/wiki/DOI): [10.1137/0221015](http://dx.doi.org/10.1137%2F0221015)
- van Lint, J. H.; Wilson, R. M. (2001),
*A Course in Combinatorics*(ấn bản 2), Cambridge University Press, [ISBN](/wiki/ISBN) [0-521-80340-3.](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-521-80340-3.)
- Marx, Dániel (2004), “Graph colouring problems and their applications in scheduling”,
*Periodica Polytechnica, Electrical Engineering* **48**(1–2), tr. 11–16, [Bản mẫu:Citeseerx](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:Citeseerx&action=edit&redlink=1) [Mycielski, J.](/w/index.php?title=Jan_Mycielski&action=edit&redlink=1)(1955), [“Sur le coloriage des graphes”](http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf), *Colloq. Math.* **3**: 161–162.
- Panconesi, Alessandro; Rizzi, Romeo (2001), “Some simple distributed algorithms for sparse networks”,
*Distributed Computing*(Berlin, New York: [Springer-Verlag](/w/index.php?title=Springer-Verlag&action=edit&redlink=1)) **14**(2): 97–100, [doi](/wiki/DOI): [10.1007/PL00008932](http://dx.doi.org/10.1007%2FPL00008932), [ISSN](/wiki/ISSN) [0178-2770](//www.worldcat.org/issn/0178-2770)
- Sekine, K.; Imai, H.; Tani, S. (1995), “Computing the Tutte polynomial of a graph of moderate size”,
*Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995)*, [Lecture Notes in Computer Science](/w/index.php?title=Lecture_Notes_in_Computer_Science&action=edit&redlink=1) **1004**, Springer, tr. 224–233, [doi](/wiki/DOI): [10.1007/BFb0015427](http://dx.doi.org/10.1007%2FBFb0015427), [ISBN](/wiki/ISBN) [3-540-60573-8](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/3-540-60573-8)
- Welsh, D. J. A.; Powell, M. B. (1967), “An upper bound for the chromatic number of a graph and its application to timetabling problems”,
*The Computer Journal* **10**(1): 85–86, [doi](/wiki/DOI): [10.1093/comjnl/10.1.85](http://dx.doi.org/10.1093%2Fcomjnl%2F10.1.85)
- West, D. B. (1996),
*Introduction to Graph Theory*, Prentice-Hall, [ISBN](/wiki/ISBN) [0-13-227828-6](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-13-227828-6)
- Wilf, H. S. (1986),
*Algorithms and Complexity*, Prentice–Hall
- Zuckerman, D. (2007), “Linear degree extractors and the inapproximability of Max Clique and Chromatic Number”,
[Theory of Computing](/w/index.php?title=Theory_of_Computing_(journal)&action=edit&redlink=1) **3**: 103–128, [doi](/wiki/DOI): [10.4086/toc.2007.v003a006](http://dx.doi.org/10.4086%2Ftoc.2007.v003a006)
- Zykov, A. A. (1949),
[“О некоторых свойствах линейных комплексов (On some properties of linear complexes)”](http://mi.mathnet.ru/eng/msb5974), *Math. Sbornik.*(bằng tiếng Nga), 24(66) (2): 163–188
- Jensen, Tommy R.; Toft, Bjarne (1995),
*Graph Coloring Problems*, John Wiley & Sons, [ISBN](/wiki/ISBN) [0-471-02865-7, 9780471028659](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-471-02865-7,_9780471028659)Kiểm tra giá trị
|isbn=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#bad_isbn))
## Liên kết ngoài[
[sửa](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&veaction=edit&vesection=21) | [sửa mã nguồn](/w/index.php?title=T%C3%B4_m%C3%A0u_%C4%91%E1%BB%93_th%E1%BB%8B&action=edit§ion=21)] [by Joseph Culberson (graph coloring programs)](http://www.cs.ualberta.ca/~joe/Coloring/index.html) *Graph Coloring Page* [by Jim Andrews and Mike Fellows is a graph coloring puzzle](http://vispo.com/software) *CoLoRaTiOn* [Links to Graph Coloring source codes](http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html) [Code for efficiently computing Tutte, Chromatic and Flow Polynomials](http://www.mcs.vuw.ac.nz/~djp/tutte/)by Gary Haggard, David J. Pearce and Gordon Royle [Graph Coloring Web Application](http://graph-coloring.appspot.com/)

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


markdown:
Thể loại:Chính trị 1654
Bách khoa toàn thư mở Wikipedia
Bước tới:
menu
,
tìm kiếm
Chủ đề Chính trị
Để biết thêm thông tin, xem
Chính trị 1654
.
Wikimedia Commons có thêm thể loại hình ảnh và phương tiện truyền tải về
Chính trị 1654
←
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
→
Thể loại này hiện không có trang hay tập tin nào.
Lấy từ “
http://vi.wikipedia.org/w/index.php?title=Thể_loại:Chính_trị_1654&oldid=11123884
”
Thể loại
:
1654
Chính trị theo năm
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
Thể loại
Thảo luận
Biến thể
Các hiển thị
Đọc
Sửa đổi
Sửa mã nguồn
Xem lịch sử
Khác
Tìm kiếm
Xem nhanh
Trang Chính
Nội dung chọn lọc
Tin tức
Bài viết ngẫu nhiên
Thay đổi gần đây
Quyên góp
Tương tác
Hướng dẫn
Giới thiệu Wikipedia
Cộng đồng
Thảo luận chung
Giúp sử dụng
Công cụ
Các liên kết đến đây
Thay đổi liên quan
Các trang đặc biệt
Liên kết thường trực
Thông tin trang
Khoản mục Wikidata
In/xuất ra
Tạo một quyển sách
Tải về dưới dạng PDF
Bản để in ra
Ngôn ngữ khác
English
Español
فارسی
Norsk bokmål
Sửa liên kết
Trang này được sửa đổi lần cuối lúc 04:54, ngày 24 tháng 3 năm 2013.
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.
Wikipedia® là thương hiệu đã đăng ký của
Wikimedia Foundation, Inc.
, một tổ chức phi lợi nhuận.
Quy định quyền riêng tư
Giới thiệu Wikipedia
Lời phủ nhận
Nhà phát triển
Phiên bản di động

WARC-Type: response

Content-Type: application/http; msgtype=response

Server: Apache

X-Content-Type-Options: nosniff

Content-language: vi

X-UA-Compatible: IE=Edge

Content-Encoding: gzip

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

Vary: Accept-Encoding,Cookie,X-Use-HHVM

Via: 1.1 varnish, 1.1 varnish

Accept-Ranges: bytes

Connection: close

X-Cache: cp1055 miss (0), cp1052 frontend miss (0)

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

X-Analytics: php=zend


markdown:
# Thể loại:Mất 1776
Bách khoa toàn thư mở Wikipedia
|
|[1770](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1770)– [1771](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1771)– [1772](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1772)– [1773](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1773)– [1774](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1774) [1775](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1775)– **1776**– [1777](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1777)– [1778](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1778)– [1779](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1779)
Thể loại này liệt kê những
**người qua đời năm 1776**. Xem thêm [những người sinh năm 1776](/wiki/Th%E1%BB%83_lo%E1%BA%A1i:Sinh_1776). **Về đầu trang** [A](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=A) [B](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=B) [C](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=C) [D](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=D) [E](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=E) [F](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=F) [G](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=G) [H](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=H) [I](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=I) [J](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=J) [K](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=K) [L](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=L) [M](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=M) [N](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=N) [O](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=O) [P](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=P) [Q](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=Q) [R](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=R) [S](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=S) [T](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=T) [U](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=U) [V](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=V) [W](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=W) [X](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=X) [Y](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=Y) [Z](//vi.wikipedia.org/w/index.php?title=Th%E1%BB%83_lo%E1%BA%A1i:M%E1%BA%A5t_1776&from=Z)
|
|![]()
[Mất 1776](//commons.wikimedia.org/wiki/Category:1776_deaths?uselang=vi)
## Các trang trong thể loại “Mất 1776”
8 trang sau nằm trong thể loại này, trên tổng số 8 trang.

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


markdown:
# Veney
Bách khoa toàn thư mở Wikipedia
[Tọa độ](/wiki/H%E1%BB%87_t%E1%BB%8Da_%C4%91%E1%BB%99_%C4%91%E1%BB%8Ba_l%C3%BD): [48°28′02″B 6°48′51″Đ / 48,4672222222°B 6,81416666667°Đ](//tools.wmflabs.org/geohack/geohack.php?language=vi&pagename=Veney¶ms=48.4672222222_N_6.81416666667_E_region:FR-54_type:city(42))
|
|
|Hành chính|
|
| ![ Quốc kỳ Pháp](//upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Flag_of_France.svg/18px-Flag_of_France.svg.png)
![ Quốc kỳ Pháp](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Flag_of_France.svg/18px-Flag_of_France.svg.png)
[Pháp](/wiki/Ph%C3%A1p) [Vùng](/wiki/V%C3%B9ng_c%E1%BB%A7a_Ph%C3%A1p) [Lorraine](/wiki/Lorraine) [Tỉnh](/wiki/T%E1%BB%89nh_c%E1%BB%A7a_Ph%C3%A1p) [Meurthe-et-Moselle](/wiki/Meurthe-et-Moselle) [Quận](/wiki/Qu%E1%BA%ADn_c%E1%BB%A7a_Ph%C3%A1p) [Quận Lunéville](/wiki/Lun%C3%A9ville_(qu%E1%BA%ADn)) [Tổng](/wiki/T%E1%BB%95ng_c%E1%BB%A7a_Ph%C3%A1p) [Tổng Baccarat](/w/index.php?title=T%E1%BB%95ng_Baccarat&action=edit&redlink=1) [Xã (thị) trưởng](/wiki/Th%E1%BB%8B_tr%C6%B0%E1%BB%9Fng)
(2008–2014)
[Độ cao](/wiki/Cao_%C4%91%E1%BB%99)
(bình quân 302 m/991 ft)
1 2(1,33 sq mi) [Nhân khẩu](/wiki/Nh%C3%A2n_kh%E1%BA%A9u_Ph%C3%A1p) 2 [Mật độ](/wiki/M%E1%BA%ADt_%C4%91%E1%BB%99_d%C3%A2n_s%E1%BB%91) 2(31 /sq mi) [INSEE](/wiki/M%C3%A3_INSEE)/Mã bưu chính [54560](http://recensement.insee.fr/searchResults.action?zoneSearchField=&codeZone=54560-COM)/ [54540](/w/index.php?title=Danh_s%C3%A1ch_c%C3%A1c_m%C3%A3_b%C6%B0u_ch%C3%ADnh_%E1%BB%9F_Ph%C3%A1p&action=edit&redlink=1) 1Dữ liệu địa chính Pháp loại trừ các hồ và ao lớn hơn 1 km² (0.386 dặm vuông hoặc 247 [acre](/wiki/Acre)) cũng như các cửa sông. 2 *Dân số không tính hai lần*: cư dân của nhiều xã (ví dụ, các sinh viên và quân nhân) chỉ tính một lần. **Veney** là một [xã](/wiki/X%C3%A3_c%E1%BB%A7a_t%E1%BB%89nh_Meurthe-et-Moselle) của [tỉnh](/wiki/T%E1%BB%89nh_(Ph%C3%A1p)) [Meurthe-et-Moselle](/wiki/Meurthe-et-Moselle), thuộc [vùng](/wiki/V%C3%B9ng_c%E1%BB%A7a_Ph%C3%A1p) [Lorraine](/wiki/Lorraine), đông bắc nước [Pháp](/wiki/Ph%C3%A1p). Xã này nằm ở khu vực có độ cao trung bình 302 [mét](/wiki/M%C3%A9t) trên [mực nước biển](/wiki/M%E1%BB%B1c_n%C6%B0%E1%BB%9Bc_bi%E1%BB%83n).
## Tham khảo[
[sửa](/w/index.php?title=Veney&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=Veney&action=edit§ion=1)] *Bạn có thể tham khảo nội dung bài này trong Wikipedia tiếng Pháp để có thêm thông tin mở rộng cho bài này. Nếu bạn không biết tiếng Pháp, có thể dùng công cụ dịch, như Google Dịch.*

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


markdown:
# Xã Newtown, Quận Delaware, Pennsylvania
Bách khoa toàn thư mở Wikipedia
|
|Xã Newtown Newtown Township
|—
| —
|
|[39°59′25″B 75°24′14″T / 39,990277777778°B 75,403888888889°T](//tools.wmflabs.org/geohack/geohack.php?language=vi&pagename=X%C3%A3_Newtown%2C_Qu%E1%BA%ADn_Delaware%2C_Pennsylvania¶ms=39.990277777778_N_-75.403888888889_E_type:city(12216)_region:US-PA_globe:earth) [Quốc gia](/wiki/Qu%E1%BB%91c_gia) [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3) [Tiểu bang](/wiki/Ti%E1%BB%83u_bang_Hoa_K%E1%BB%B3) [Pennsylvania](/wiki/Pennsylvania) [Quận](/w/index.php?title=Danh_s%C3%A1ch_c%C3%A1c_qu%E1%BA%ADn_%E1%BB%9F_Pennsylvania&action=edit&redlink=1) [Quận Delaware](/wiki/Qu%E1%BA%ADn_Delaware,_Pennsylvania) **Dân số**(2010) [Múi giờ](/wiki/M%C3%BAi_gi%E1%BB%9D) [EST](/wiki/M%C3%BAi_gi%E1%BB%9D_mi%E1%BB%81n_%C4%90%C3%B4ng_(B%E1%BA%AFc_M%E1%BB%B9))( [UTC-5](/wiki/UTC-5)) [DST](/wiki/Quy_%C6%B0%E1%BB%9Bc_gi%E1%BB%9D_m%C3%B9a_h%C3%A8)) **EDT**( [UTC-4](/wiki/UTC-4)) **Xã Newtown** ( [tiếng Anh](/wiki/Ti%E1%BA%BFng_Anh): *Newtown Township*) là một [xã](/wiki/X%C3%A3_c%E1%BB%A7a_Hoa_K%E1%BB%B3) thuộc [quận Delaware](/wiki/Qu%E1%BA%ADn_Delaware,_Pennsylvania), tiểu bang [Pennsylvania](/wiki/Pennsylvania), [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3). Năm 2010, dân số của xã này là 12.216 người. [[1]](#cite_note-1)
## Tham khảo[
[sửa](/w/index.php?title=X%C3%A3_Newtown,_Qu%E1%BA%ADn_Delaware,_Pennsylvania&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=X%C3%A3_Newtown,_Qu%E1%BA%ADn_Delaware,_Pennsylvania&action=edit§ion=1)] [^](#cite_ref-1) [“2010 Census Gazetteer Files”](http://www.census.gov/geo/www/gazetteer/gazetteer2010.html). [Cục Thống kê Dân số Hoa Kỳ](/wiki/C%E1%BB%A5c_Th%E1%BB%91ng_k%C3%AA_D%C3%A2n_s%E1%BB%91_Hoa_K%E1%BB%B3). Truy cập ngày 8 tháng 10 năm 2012.

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