Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
BÀI 09: Giả sử G là đồ thị hai phần có n đỉnh
tailieunhanh - BÀI 09: Giả sử G là đồ thị hai phần có n đỉnh
Giả sử G là đồ thị hai phần có n đỉnh. Ký hiệu k là số phần tử của tập đỉnh tựa bé nhất. Khi đó thì: Định lý : 1. Số ổn định trong của đồ thị hai phần G là bằng n-k. 2. Số phần tử của cặp ghép lớn nhất của G là bằng k. Chứng minh: 1. Suy từ nhận xét trên: C là tập đỉnh tựa nhỏ nhất ⇔ V \ C là tập ổn định trong lớn nhất. | BÀI 09 Giả sử G là đồ thị hai phần có n đỉnh. Ký hiệu k là số phần tử của tập đỉnh tựa bé nhất. Khi đó thì Định lý 1. Số ổn định trong của đồ thị hai phần G là bằng n-k. 2. Số phần tử của cặp ghép lớn nhất của G là bằng k. Chứng minh 1. Suy từ nhận xét trên C là tập đỉnh tựa nhỏ nhất V C là tập ổn định trong lớn nhất. 2. Giả sử W là cặp ghép lớn nhất và C là tập tựa nhỏ nhất. Lập ánh xạ t W C như sau Ve G W t e là một đỉnh của e thuộc C. Đỉnh đó tồn tại vì C là tập tựa còn nếu cả hai đỉnh của e đều thuộc C thì ta lấy một trong hai đỉnh đó. Nếu u v G W và u z v thì t u z t v vì hai cạnh u và v không có đỉnh chung. Vậy thì W C k. Hình . Cách xây dựng ánh xạ t Để chứng minh chiều ngược lại ta xây dựng tập đỉnh tựa C từ cặp ghép lớn nhất W mà hai tập này có cùng lực lượng. Ký hiệu B là tập các đỉnh của W trong V1. Lập ánh xạ h B V2 như sau Va G B S b G V2 a b G W ta đặt h a b. Vậy h B chính là tập các đỉnh của W trong V2. Nếu a c G B và a z c thì h a z h c vì các cạnh trong W chứa a và c không kề nhau. Hình . Cách xây dựng tập đỉnh tựa Một đường đi trong đồ thị G được gọi là đường đan nếu nó có dạng Wj Uj w2 u2 . wq uq trong đó w w2 . wq đều thuộc W và UỊ u2 . uq đều không thuộc W. Ký hiệu B1 a G B I 3 đường đan đi từ a đến một đỉnh nào đó nằm ngoài B và B2 B B1. Đặt C B2 u h B1 . Chúng ta sẽ chứng minh rằng tập C là tập đỉnh tựa của đồ thị G. Ta chứng minh điều này bằng phản chứng. Giả sử rằng tập C không phải tập đỉnh tựa của đồ thị hai phần G nghĩa là có cạnh a b nào đó không tựa vào tập C. Vậy thì a t B2 và b t h B1 . Nhưng vì tập các cạnh W là cặp ghép lớn nhất nên cạnh a b phải kề với một cạnh nào đó trong W nghĩa là a E B hoặc b E h B . Xét các trường hợp sau đây 1 Trường hợp a E B. Suy ra a E B1. Khi đó có một đường đan X Wj UỊ w2 u2 . wq uq dẫn đỉnh a tới một đỉnh d nào đó nằm ngoài tập B. - Nếu b t h B thì cạnh a b t W. Ta loại các cạnh Mị w2 . wq ra khỏi W và thay các cạnh a b U1 u2 . uq vào W. Khi đó W vẫn là một cặp ghép và số cạnh tăng thêm 1. .
Hữu Khang
120
5
pdf
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Bấm vào đây để xem trước nội dung
Tải xuống
TÀI LIỆU LIÊN QUAN
Chương 5: Cặp ghép và đồ thị hai phần
4
126
2
Giáo trình đồ thị - Cặp ghép và đồ thị hai phần
4
76
0
BÀI 09: Giả sử G là đồ thị hai phần có n đỉnh
5
96
0
Bài giảng Toán rời rạc: Đồ thị - Trần Vĩnh Đức
57
35
2
Ebook Lý thuyết đồ thị: Phần 2
123
66
5
Bài giảng Toán rời rạc: Ghép cặp trên đồ thị hai phần - Trần Vĩnh Đức
39
52
3
Tuyển chọn các bài toán về hàm số: Phần 1 (Khóa luyện thi 2015 - 2016) - Đặng Việt Hùng
41
102
5
Đề cương chi tiết học phần Toán rời rạc và lý thuyết đồ thị (Discrete mathematics and Graph theory)
9
41
1
Bài giảng Toán rời rạc: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức
44
64
2
Dạy học toán theo định hướng phát triển tư duy đồ thị dưới sự hỗ trợ của phần mềm Geogebra
10
127
3
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461974
55
Giới thiệu :Lập trình mã nguồn mở
14
23288
67
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
11015
533
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10226
452
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9583
106
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8441
1138
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8303
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7900
2239
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6876
257
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
6252
1518
TỪ KHÓA LIÊN QUAN
Toán học
đồ thị hai phần
số ổn định của đồ thị
cặp ghép
phần tử cặp ghép
bài toán phân công nhiệm vụ
Tập đỉnh tựa
đồ thị vô hướng
đồ thị
giáo trình đồ thị
tài liệu về đồ thị
ứng dụng của đồ thị
Bài giảng Toán rời rạc
Toán rời rạc
Đồ thị đầy đủ
Đồ thị vòng
Đồ thị bánh xe
Ebook Lý thuyết đồ thị
Cặp ghép và đồ thị hai phần
Bài toán đường đi ngắn nhất
Bài toán mạng vận tải
Đồ thị phẳng
Cây nhị phân
Ghép cặp trên đồ thị hai phần
Định lý Hall
Ghép cặp cực đại
Ghép cặp hai phía
Tuyển chọn các bài toán về hàm số
Luyện thi Đại học môn Toán
Tiếp tuyến của đồ thị hàm số
Sự tương giao của hai đồ thị
Đồ thị hàm số
Bài tập hàm số
Đề cương Toán rời rạc
Đề cương lý thuyết đồ thị
Lý thuyết đồ thị
Quan hệ hai ngôi
Tô màu đỉnh của đồ thị
Thuật toán tham lam tô màu đỉnh
Thuật toán tham lam
Tư duy đồ thị
Toán trắc nghiệm
Hàm số bậc hai
Phần mềm Geogebra
Đại số lớp 10
Chương trình toán trung học phổ thông
Luận văn Thạc sĩ
Luận văn Thạc sĩ Quản lý đất đai
Quản lý đất đai
Phần mềm Gcadas
Phần mềm Microstation v8i
Bản đồ địa chính
Sách Toán học
Tài liệu Toán phổ thông
Ôn tập Toán lớp 10
Chuyên đề hàm số bậc nhất
Chuyên đề hàm số bậc hai
Đồ thị của hàm số
Tập xác định của hàm số
Vẽ đồ thị hàm số
Trắc nghiệm Toán lớp 10
Bài tập Đại số lớp 10
Trắc nghiệm Đại số 10
Ôn tập hàm số bậc nhất
Bài tập về hàm số bậc hai
Khái niệm hàm số
Ứng dụng phần mềm GCADAS
Ứng dụng phần mềm Microstation V8I
Thành lập bản đồ địa chính
Bài giảng Tin học đại cương
Tin học đại cương
Chèn đồ thị vào bảng tính
Thêm dữ liệu
Đường hồi quy
Thành phần của đồ thị
Khoá Luận tốt nghiệp Đại học
Quản lý Tài nguyên
Đô thị cổ Hội An
Hội thảo quốc tế về đô thị cổ Hội An
Lịch sử Hội An
Giao Chỉ quốc mậu dịch độ hải đồ
Bản sắc địa văn hóa Hội An
Địa mạo khu vực Hội An
đề thi thử đại học 2010
giáo dục
đào tạo
ôn thi đại học cao đẳng
tài liệu luyện thi đại học
đề thi thử đại học môn Toán
đáp án đề thi đại học
luyện thi đại học 2010
thử sức trước kỳ thi đại học
Để học tốt Toán 9
Đại số 9
Căn bậc hai
Căn bậc ba
Hàm số bậc nhất
Đồ thị hàm số bậc nhất
Căn bậc N
H phương trình bậc nhất hai ẩn số
Hệ phương trình tương đương
Lập hệ phương trình
Giải hệ phương trình bằng phương pháp thế
Tài liệu ôn thi Đại học
Khảo sát và vẽ đồ thị hàm số chuẩn
Chuyên đề luyện thi Đại học
Luyện thi ĐH môn Toán 2015
Ôn thi Đại học 2015
TÀI LIỆU MỚI ĐĂNG
Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 4
47
269
1
29-05-2024
Management and Services Part 1
10
172
0
29-05-2024
báo cáo hóa học:" Endoscopic decompression for intraforaminal and extraforaminal nerve root compression"
7
120
0
29-05-2024
XỬ TRÍ CHẤN THƯƠNG SỌ NÃO KÍN
1
127
1
29-05-2024
Hệ thống làm lạnh và điều hòa không khí
21
138
0
29-05-2024
báo cáo hóa học:" Journal of the International AIDS Society: an important step forward"
2
94
0
29-05-2024
Thương hiệu sản phẩm làng nghề: Đã ít, lại thiếu tính cạnh tranh
5
127
0
29-05-2024
Quy Trình Canh Tác Cây Bông Vải
8
119
0
29-05-2024
Điều bạn cần làm để giữ chặt tình yêu
5
115
0
29-05-2024
Chương 10: Các phương pháp tính quá trình quá độ trong mạch điện tuyến tính
57
188
4
29-05-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7900
2239
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
6252
1518
Ebook Chào con ba mẹ đã sẵn sàng
112
3852
1275
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5467
1141
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8441
1138
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3573
658
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3773
567
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
11015
533
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4211
526
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4217
483
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.