Đề tài Vectơ bậc đồ thị

g x1 kề với d1 dỉnh kế tiếp trong dãy x2, x3, ..., xn. 
 Giả sử điều đó không đúng. Khi đó tồn tại j, k thoả 
2 < j £ d1 + 1 < k & x1 không kề xj & x1 kề xk
 Nếu dj = dk, thì ta có thể hoán vị hai đỉnh xj và xk để cho x1 kề xj. Vì vậy giả thiết dj > dk.
 Như vậy tổng các bậc của các đỉnh kề x1 là dk + t với t ³ 0. Vì dj > dk , nên tồn tại đỉnh xi kề xj mà không kề xk. Ta xây dựng đồ thị H từ đồ thị G bằng cách loại bỏ hai cạnh (xi, xj), (x1, xk) và thêm vào hai cạnh (xi, xk), (x1, xj). Đồ thị H cũng có vectơ bậc d(H) = v và tổng các bậc của các đỉnh kề x1 là dj + t > dk + t. Điều này mâu thuẫn với việc chọn đồ thị G có tổng các bậc của các đỉnh kề x1 là lớn nhất.
 Bây giờ ta xây dựng đồ thị G’ từ đồ thị G bằng cách loại đỉnh x1 và các cạnh liên thuộc x1. Hiển nhiên vectơ bậc d(G’) = v1, tức v1 là vectơ đồ thị. Suy ra đpcm.
 3. Bài toán vectơ bậc đồ thị
	Cho v = [d1, d2, ..., dn], n ³ 2, là vectơ n số tự nhiên thoả
n - 1 ³ d1 ³ d2 ³ ... ³ dn ³ 0
	Hãy kiểm tra xem v có phải là vectơ bậc đồ thị hay không ?
 Ø Giải pháp: Sử dụng định lý Hakimi-Havel ta có thể đưa ra thuật toán kiểm tra xem một vectơ có phải là vectơ đồ thị không như sau.
 4. Thuật toán
 ¸ Đầu vào : Vectơ v = [d1, d2, ..., dn] gồm n số nguyên giảm dần.
 ¸ Đầu ra : kết luận v là vectơ đồ thị hay v không là vectơ đồ thị.
 ¸ Các bước :
 Bước 0. (Khởi tạo) Đặt k := n và u := v = [d1, d2, ..., dk]
 Bước 1. Nếu u có thành phần lớn hơn (k - 1) hoặc nhỏ hơn 0, thì sang bước 4.
 Bước 2. Nếu các thành phần của u đều là số 0, thì sang bước 5.
 Bước 3. (bước lặp) Cho u’ là vectơ nhận được từ u bằng cách bỏ thành phần d1, và trừ bớt 1 trong d1 thành phần tiếp theo. Ký hiệu u1 là vectơ u’ trong đó các thành phần được sắp xếp giảm dần. Đặt k := k-1 và u := u1. Quay lại bước 1.
 Bước 4. Kết luận: v không phải là vectơ đồ thị. Kết thúc.
 Bước 5. Kết luận: v là vectơ đồ thị. Kết thúc.
 Ví dụ: Kiểm tra vectơ v = [4, 3, 3, 2, 2].
	Bước 0: Đặt k :=5, u = [4, 3, 3, 2, 2].
	Bước lặp 1: k = 5, u = [4, 3, 3, 2, 2], u’ = [2, 2, 1, 1], u1 = [2, 2, 1, 1]
	Bước lặp 2: k = 4, u = [2, 2, 1, 1], u’ = [1, 0, 1], u1 = [1, 1, 0]
	Bước lặp 3: k = 3, u = [1, 1, 0], u’ = [0, 0], u1 = [0, 0]
	Kết luận v là vectơ đồ thị. Đồ thị sau có vectơ bậc là v
Chương 2: PHÂN TÍCH VÀ THIẾT KẾ
 1. Cấu trúc dữ liệu
 Đề tài Vectơ Bậc Đồ Thị sử dụng kiểu mảng một chiều, và kiểu File – văn bản để cài đặt thuật toán.
 1.1 Mảng 1 chiều
 - Khai báo kiểu: Type = array [ KCD ] of KPT ;
KCD : kiểu chỉ dẫn có thể kiểu byte, char, Boolean, liệt kê, miền con. KCD quy định cấu trúc mảng và cách thức truy nhập đến các phần tử của mảng.
KPT : là kiểu đơn giản hoặc có cấu trúc.
 - Khai báo biến:
 Gián tiếp: Var : ;
 Trực tiếp: Var : array [KCD] of ;
 Chú ý : Có thể gán 1 biến mảng cho 1 biến mảng khác cùng kiểu.
 1.2 Kiểu File – văn bản
 * Một số thủ tục và các hàm chung 
 1.2.1 Một số thủ tục
 - Gán tên file
 ASSIGN(F, filename); 
 Gán một file trên đĩa có tên là filename cho biến F,mọi truy xuất trên file cụ thể được thực hiện thông qua biến file này.
 - Mở một file mới 
 REWRITE(F); mở file mới rỗng
 Tạo file mới có tên đã gán cho biến file F. Nếu file đã có trên đĩa thì mọi dữ liệu trên đó sẽ bị xoá và con trỏ file ở vị trí đầu tiên của file.
 - Mở file đã có trên đĩa
 RESET(F);
 Mở file có tên đã gán cho biến file F. Nếu file chưa có trên đĩa thì chương trình sẽ dừng vì gặp lỗi xuất/ nhập
 - Đọc dữ liệu 
 Read(F, các biến); 
 Readln(F, các biến);
 - Ghi dữ liệu 
 Write(F, các biến); 
 Writeln(F, các biến);
 - Đóng file 
 Close(F);
 1.2.2 các hàm chung
 - Hàm kiểm tra cuối file
 Eof(F);trả về giá trị true hoặc false
 - Hàm kiểm tra cuối dòng	
 Eoln(F);trả về giá trị true hoặc false
 2. Thiết kế và giải thuật
 Dựa vào thuật toán kiểm tra một vectơ ta có thể thiết kế và giải thuật thuật toán đó như sau: 
 ¸ Đầu vào : Vectơ v = [d1, d2, ..., dn] gồm n số nguyên giảm dần.
 ¸ Đầu ra : kết luận v là vectơ đồ thị hay v không là vectơ đồ thị.
 ¸ Các bước: 
Khởi tạo: Đặt k:= n, u:= v = [d1, d2, ..., dk]
Kiểm tra vectơ: 
 For i:= 1 To k Do
      Nếu (u[i] > k - 1) hoặc ( u[i] < 0 ) thì vt:=false
 Ngược lại nếu u[i] = 0 thì vt:= true
 Ngược lại nếu u[i] 0 thì
 For i:= 1 To u[1] Do
 u’[i]:= u[i+1] - 1;
 For i:= u[1] + 1 To k - 1 Do
 u’[i]:= u[i+1];
 Đặt u1:=u’{các thành phần đã được sắp xếp giảm dần}
 Đặt k:=k-1, u:=u1;
 Lặp (Kiểm tra vectơ)
 Kết thúc.
Mở file để ghi vectơ đồ thị:
 Nếu vt:=true thì kết luận vectơ v là vectơ đồ thị
 Ngược lại vt:=false thì kết luận vectơ v không là vectơ đồ thị.
3. Sơ đồ khối
 3.1 Sơ đồ kiểm tra vecto đã sắp xếp chưa
BEGIN
k:=1
k < n;
v[k] ≤ v[k+1]
Inc(k)
Đúng
Sai
k = n
S_xep:= true
S_xep:= false
END
Đúng
Sai
3.2 Sơ đồ sắp xếp theo chiều giảm dần
BEGIN
i:= 1;
i ≤ n;
k:= i+1;
k ≤ n;
v[i] < v[k]
h_vị (v[i], v[k]);
{h_v ị: tam:= x; x:= y; y:= tam;}
END
3.3 Sơ đồ kiểm tra vectơ đồ thị
sai
BEGIN
vt:= true;
kvt:= false
i:= 1; i < n
v[i] > n-1 or
v[i] < 0
đúng
sai
đúng
vt:= false
v[i] 0
Begin
u[i]:= v[i+1]
i:= v[1] + 1; i < n-1
u[i]:= v[i+1] - 1
i:= 1; i < v[1];
not S_xep (u, n- 1) 
sxgiam_dan (u, n- 1)
Kiemtra:= Kiemtra (u, n- 1)
kvt:= true
Kiemtra:
= true
Kiemtra:
= false
END
BEGIN
assign(f, ‘VECTO.INP); reset (f);
assign(g, ‘VECTO.OUT); rewrite (g);
not eof (f)
close (f);
close (g);
END
đúng
inc (n)
Begin
readln (f, v [n])
end
not 
kiemtra(v,n)
Begin
sai
đúng
writeln
(g,‘NO’)
Begin
n:= 0
not eoln (f)
sai
đúng
readln (f)
writeln
(g,‘YES’)
end
end
3.3 Sơ đồ tạo file dữ liệu đầu vào, xuất ra vectơ đồ thị
sai
4. Cấu trúc chương trình
 + Các chương trình con được sử dụng thủ tục và hàm có cấu trúc như sau:
 * Hàm: Funtion Tenham (TS1: Kieu; ....): Kieu;
 Var các biến; 
 Begin
 Các lệnh tính toán;
 ...;
 Tenham:= gia tri;
 End;
 * Thủ tục: Procedure Tenthutuc(TS1: Kieu;...; Var TS2: Kieu; var TS3: Kiểu;...); 
 Var các biến;
 Begin
 Các lệnh;
 ...;
 End; 
 + File dữ liệu đầu vào (VECTO.INP) có cấu trúc:
	a1, a2, . . . . , ak
	b1, b2, . . . . , bm
	d1, d2, . . . . , dn
 + File kết quả đầu ra(VECTO.OUT) có cấu trúc: 
	YES (nếu V là vectơ đồ thị)
	NO (nếu V không là vectơ đồ thị)
 + File chương trình nguồn:VECTO.PAS
 + File chương trình dịch : VECTO.EXE
Chương 3: CÀI ĐẶT VÀ SỬ DỤNG THUẬT TOÁN
 1. Giới thiệu ngôn ngữ lập trình
 Pascal là ngôn ngữ lập trình cấp cao do Niklaus Wirth – người Thuỵ Sỹ thiết kếvào đầu năm 1970, với tên Pascal để kỷ niệm nhà toán học người Pháp Balaise Pascal. 
 Ngôn ngữ lập trình Pascal có ưu điểm là ngữ pháp, ngữ nghĩa đơn giản và có tính logic; câu trúc chương trình rõ ràng, dễ hiểu; dễ sữa chữa, cải tiến. Có thể nói tính cấu trúc của Pascal được thể hiện trên ba mặt:
 1. Dữ liệu: từ các dữ liệu đã có, có thể xây dựng thành các kiểu dữ liệu phức tạp.
 2. Lệnh: từ các lệnh đã có, có thể nhóm chúng lại với nhau và đặt giữa hai từ khóa Begin và End thành lệnh ghép.
 3. Chương trình: một chương trình có thể chia thành nhiều chương trình con.
 Từ những ưu điểm trên, nhóm chúng em sử dụng ngôn ngữ lập trình Pascal cho chương trình.
 2. Chức năng và giao diện chương trình
 2.1 Chức năng
 Chương trình được cài đặt nhằm mục đích kiểm tra một vectơ có phải là một vectơ đồ thị hay không. 
 2.2 Giao diện của chương trình
 Chương trình được cài đặt và chạy trên môi trường Turbo Pascal.Exe. Khi nhập n vecto vào file VECTO.INP thì khi chạy chương trình này ta thu được kết quả trên file VECTO.OUT.
 Giao diện chính của chương trình, đầu tiên ta nhập các vecto có dạng
 v = [d1, d2, ..., dn] vào file VECTO.INP với giao diện:
 File kết quả VECTO.OUT ta thu được với giao diện
 2.3 Cài đặt chương trình
PROGRAM VECTO_BAC_DO_THI;
TYPE vecto= array[1..50] of integer;
VAR f, g: text;
 v: vecto; n: integer;
PROCEDURE giamdan(var u: vecto; m: integer);
VAR i, j, tam: integer;
BEGIN
 FOR i:=1 to m-1 do
 FOR j:= i+1 to m do
 if u[i] < u[j] then
 BEGIN
 tam:= u[i];
 u[i]:= u[j];
 u[j]:= tam;
 END;
END;
FUNCTION kiemtra(v: vecto; m: integer): boolean;
VAR i: integer; u: vecto; vt, kvt: boolean;
BEGIN
 u:= v;
 giamdan(u,m); kvt:= false; vt:= true;
 FOR i:= 1 to m do
 if ( u[i] > m-1) or ( u[i] < 0) then kvt:= true
 else if u[i] 0 then vt:= false;
 if kvt then kiemtra:= false
 else if vt then kiemtra:= true
 else 
 begin
 for i:= 1 to u[1] do u[i]:= u[i+1] -1;
 for i:=u[1] + 1 to m-1 do u[i]:= u[i+1];
 giamdan(u,m-1);
 kiemtra:= kiemtra(u,m-1);
 end;
end;
 BEGIN
 Writeln('chuong trinh xac dinh vecto do thi');
 assign( f,'VECTO.INP' ); reset(f);
 assign( g,'VECTO.OUT' ); rewrite(g);
 while not eof(f) do
 begin
 n:=0;
 while not eoln(f) do
 begin 
 inc(n);
 read(f,v[n]);
 write(v[n]:3);
 end;
 writeln;
 if kiemtra(v,n) then writeln( g,'YES' )
 else writeln( g,'NO' );
 readln(f);
 end;
 close(f);close(g);
 END.
 2.4 Kết quả chạy chương trình
 Dữ liệu được lấy từ tệp VECTO.INP, gồm các vectơ dạng v = (a1, a2, . . .,ak) sắp xếp giảm dần và viết theo dòng. Chương trình sẽ kiểm tra vectơ v và kết quả được lưu vào tệp VECTO.OUT. Nếu v là vectơ đồ thị thì kết quả là YES, ngược lại là NO.
 Ví dụ: 
 file vào :( VECTO.INP)
 file ra tương ứng:( VECTO.OUT)
PHẦN KẾT LUẬN
 Nhờ chương trình kiểm tra vectơ đồ thị bằng Pascal mà ta có thể kiểm tra xem một vecto có phải vectơ đồ thị hay không một cách dễ dàng hơn.
 Qua quá trình học lí thuyết và thực hành trên máy với sự giúp đỡ hướng dẫn tận tình của thầy giáo Trần Quốc Chiến nhóm chúng em đã tiếp thu, tiến hành học nhóm, trao đổi và hoàn thành đề tài vectơ bậc đồ thị của bộ môn Lí Thuyết Đồ Thị.Với những hạn chế về kiến thức và thời gian nên nhóm chúng em không tránh khỏi thiếu sót trong quá trình thực hiện đề tài. Rất mong được sự thông cảm và chỉ bảo của thầy.
TÀI LIỆU THAM KHẢO
 1. Giáo trình Lí Thuyết Đồ Thị và ứng dụng PGS.TSKH Trần Quốc Chiến
 2. Giáo trình Turbo Pascal 7.0 PGS.TS Bùi Thế Tâm
 3. Giáo trình tin học đại cương chuyên Đoàn Duy Bình
 4.