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
Tài liệu HOT
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
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
TAILIEUCHUNG - 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
117
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
126
3
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461887
55
Giới thiệu :Lập trình mã nguồn mở
14
22723
61
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
10906
530
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10083
447
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
9540
104
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8302
1127
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8248
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7867
2220
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6713
253
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
5795
1391
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
Mass Transfer in Multiphase Systems and its Applications Part 19
40
258
1
01-05-2024
CẤU TẠO HẠT NHÂN NGUYÊN TỬ-ĐỘ HỤT KHỐI-NĂNG LƯỢNG LIÊN KẾT-LK RIÊNG
12
270
0
01-05-2024
beginning Ubuntu Linux phần 1
34
213
1
01-05-2024
Trading Strategies Profit Making Techniques For Stock_3
23
185
0
01-05-2024
Magnetic Bearings Theory and Applications phần 2
14
173
0
01-05-2024
THE ANTHROPOLOGY OF ONLINE COMMUNITIES BY Samuel M.Wilson and Leighton C. Peterson
19
148
0
01-05-2024
BÀI GIẢNG VỀ - MẠCH ĐIỆN II - Chương I: Phân tích mạch trong miền thời gian
38
143
0
01-05-2024
Hướng dẫn sử dụng Quickoffice cho Ipad và Iphone
13
153
0
01-05-2024
Đề tài: Tìm hiểu một số yêu cầu đặt ra với một phòng thu âm, để đảm bảo chất lượng âm thanh trong sản phẩm đa phương tiện
8
161
1
01-05-2024
báo cáo hóa học:" Endoscopic decompression for intraforaminal and extraforaminal nerve root compression"
7
107
0
01-05-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7867
2220
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
5795
1391
Ebook Chào con ba mẹ đã sẵn sàng
112
3772
1233
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5334
1136
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8302
1127
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3518
644
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
10906
530
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3695
525
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4071
516
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4136
480
Đã 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.