Tiểu luận tìm cây phủ chiều ngang

Add your review

14.000

Add to wishlistAdded to wishlistRemoved from wishlist 0

14.000

Tiểu luận tìm cây phủ chiều ngang

Tiểu luận tìm cây phủ chiều ngang

fff

Tiểu luận tìm cây phủ chiều ngang

fff

Tiểu luận tìm cây phủ chiều ngang

fff

Tiểu luận tìm cây phủ chiều ngang

fff

Tiểu luận tìm cây phủ chiều ngang

fff

Tiểu luận tìm cây phủ chiều ngang

fff

ĐẠI HỌC ĐÀ NẲNG TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NÀNG —V9WIO Q CSCSCÍ—

TIÊU LUẬN

MÓN: TOÁN ỨNG DỤNG

ĐÈ TÀI

THUẬT TOÁN TÌM CÂY PHỦ THEO CHIÊU

NGANG

GVhướng dẩn

Học viên c ‘huyên ngành Khóa


PGS.TSKH. Trần Quốc Chiến Nguyễn Trọng Ân Khoa Học Máy Tính

30

ĐÀ NẰNG, 06/2015

LỜI MỎ ĐÀU

Lý thuyết đồ thị là một lĩnh vực nghiên cúu đà có từ lâu và có nhiều ứng dụng trong ngành công nghệ thông tin. Những tư tưởng cơ bân Tiểu luận tìm cây phủ chiều ngang của lý thuyết đổ thị được đề xuất vào những năm đầu cúa thế kỳ 18 bời nhà toán học lỗi lạc người Thụy Sỳ: Leonhard Euler. Chinh ông là người đà sử dụng đồ thị đế giãi bài toán nôi tiếng về 7 cái cầu ở thành phố Konigberg.

Lý thuyết đồ thị có rất nhiều bài toán đưọc ứng dụng có hiệu quá trong nhiều lình vực. Một trong những bài toán đó chính là bãi toán tim cày phũ cùa đồ thị.

Đế ứng dụng Tiểu luận tìm cây phủ chiều ngang phần lý thuyết đà học về Toán ứng dụng vào trong đề tài cũa tiểu luận, em trinh bây hai vấn đề :

J Thuật toán tìm cây phu của đồ thị theo chiều ngang.

J Áp dụng thuật toán trên cho đồ thị không liên thông.

Em xin chân thành căm ơn thầy PGS.TSKH. Tran Quốc Chiến đà hướng dần và cung cấp kiến thức và tài liệu đề em có thể hoàn thành tiều luận này.

Học viên thực hiện

Nguyên Tiểu luận tìm cây phủ chiều ngang Trọng Ân

MỤC LỤC

LỜI MỠ ĐẢƯ

CHƯƠNG 1

ĐẠI CƯƠNG VE ĐO THỊ

CÀY

  • 2.  Địnli lý 1……………………………………………………3 Tiểu luận tìm cây phủ chiều ngang

CÂY PHÚ

4

CHƯƠNG II

BÃI TOÁN TÌM CÂY PHỬ THEO CHIẺƯ NGANG

CHƯƠNG III

THIÊT KÊ VÀ CÀI ĐẶT BÀI TOÁN

  • 2.  Dữ liệu đau ra……………………………………………….. Tiểu luận tìm cây phủ chiều ngang 6

ây phũ SpaimingTree

l.Ỷ tường

KÉT LUẬN

TÀI LIỆU THAM KHAO

CHƯƠNG I

ĐẠI CƯƠNG VẾ ĐÒ THỊ

CÂY

I. Định nghĩa

1. Định nghĩa 1

Cày là đồ thị liên thòng không chứa chu trình.

Ví dụ 3.1.1. Đồ thị sau Tiểu luận tìm cây phủ chiều ngang là cây

Gốc cua cây là một đinh đặc biệt, thòng thường là đinh trên cùng.

Mừc của đinh là độ dài đường đi từ gốc lên đinh đó.

Độ cao cúa cây là mức lớn nhất cùa cây (tức mức cùa đinh cách xa gốc nhất). Trong vi dụ trên nếu ta chọn Vi là gốc thì V2, V3 là nhùng định mức 1, các đinh V4, V5, v<s, V? có mức 2, và Tiểu luận tìm cây phủ chiều ngang độ cao cúa cây là 2

  • 2. Định nghĩa 2

Cho T là cây có gốc Vo. Già $ữ X, y, z là đinh của T và (Vo, V.,Vn) là đường đi tir Vo đến V., trong T. khi đó ta gọi

Vn.i là cha cua Va

Vo,Vn-I là tiền bối cùa vn

Vn là con cúa Vn.i

y lả hậu thế cua X. nếu X lã tiền bối cua Tiểu luận tìm cây phủ chiều ngang y y và z là anh em nếu chúng đều là con của đinh X

X là đinh lá nếu nó không có con

X là đinh trong cùa cây nếu nó có con

  • 3. Định nghĩa 3

Rìmg là đồ thị mà mồi thành phần liên thông lã cây.

Vi dụ 3.1.2. Đồ thị sau là rừng có 3 cây

II. Tính chất

  • 1. Định lý 1 (Định lý tương đương)

Cho T là đồ Tiểu luận tìm cây phủ chiều ngang thị n đinh. Các mệnh đề sau tương đương

T là cây.

T không chứa chu trình và có n-1 cạnh.

T liên thòng và có n-1 cạnh.

T liên thông và mỗi cạnh là cằu.

Hai đinh bất kỳ được nổi với nhau bởi một đường đi duy nhất.

T không chứa chu trình và nếu thêm một cạnh nối hai đinh thì ta thu dược đúng 1 chu trinh

T liên thông và nếu them một Tiểu luận tìm cây phủ chiều ngang cạnh nối hai đinh thi ta thu được đúng 1 chu trình

  • 2.  Định lý 2

Tâm của cây lã tập hợp hoặc chi có một đinh hoặc có hai đinh kề nhau.

2

0

User Reviews

0.0 out of 5
0
0
0
0
0
Write a review

There are no reviews yet.

Be the first to review “Tiểu luận tìm cây phủ chiều ngang”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Vendor Information

  • No ratings found yet!
Added to wishlistRemoved from wishlist 0
phân tích tình hình kinh doanh xuất khẩu gạo của công ty cổ phần gentraco
Added to wishlistRemoved from wishlist 0
46.000
Added to wishlistRemoved from wishlist 0
Tăng cường công tác quản lý nhà nước về dân tộc trên địa bàn huyện Võ Nhai.
Added to wishlistRemoved from wishlist 0
50.000
Added to wishlistRemoved from wishlist 0
Luận văn thạc sĩ tranh chấp và giải quyết tranh chấp hợp đồng nhượng quyền thương mại theo pháp luật việt nam 07
Added to wishlistRemoved from wishlist 0
198.000
Added to wishlistRemoved from wishlist 0
(Luận văn thạc sĩ) đánh giá thực trạng nước thải trên địa bàn thị xã sông công tỉnh thái nguyên
Added to wishlistRemoved from wishlist 0
98.000
Sold by
@ xcnguyen220
Tiểu luận tìm cây phủ chiều ngang
Tiểu luận tìm cây phủ chiều ngang
Kho Thư Viện
Logo
Shopping cart