markdown:
# Cấu trúc dữ liệu 2005 P13
Chia sẻ: Nhan Hoang | Ngày: | Loại File: PDF | Số trang:26
lượt xem 9
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091110/nguyen2/80x100/ctdl_2005_chuong_13_4923.jpg)
##
Cấu trúc dữ liệu 2005 P13
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Tham khảo tài liệu 'cấu trúc dữ liệu 2005 p13', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Cấu trúc dữ liệu 2005 P13
- Chöông 13 – Ñoà thò Chöông 13 – ÑOÀ THÒ Chöông naøy trình baøy veà caùc caáu truùc toaùn hoïc quan troïng ñöôïc goïi laø ñoà thò. Ñoà thò thöôøng ñöôïc öùng duïng trong raát nhieàu lónh vöïc: ñieàu tra xaõ hoäi, hoùa hoïc, ñòa lyù, kyõ thuaät ñieän,…. Chuùng ta seõ tìm hieåu caùc phöông phaùp bieåu ñieãn ñoà thò baèng caùc caáu truùc döõ lieäu vaø xaây döïng moät soá giaûi thuaät tieâu bieåu lieân quan ñeán ñoà thò. 13.1. Neàn taûng toaùn hoïc 13.1.1. Caùc ñònh nghóa vaø ví duï Moät ñoà thò (graph) G goàm moät taäp V chöùa caùc ñænh cuûa ñoà thò, vaø taäp E chöùa caùc caëp ñænh khaùc nhau töø V. Caùc caëp ñænh naøy ñöôïc goïi laø caùc caïnh cuûa G. Neáu e = (ν, µ) laø moät caïnh coù hai ñænh ν vaø µ, thì chuùng ta goïi ν vaø µ naèm treân e, vaø e noái vôùi ν vaø µ. Neáu caùc caëp ñænh khoâng coù thöù töï, G ñöôïc goïi laø ñoà thò voâ höôùng (undirected graph), ngöôïc laïi, G ñöôïïc goïi laø ñoà thò coù höôùng (directed graph). Thoâng thöôøng ñoà thò coù höôùng ñöôïc goïi taét laø digraph, coøn töø graph thöôøng mang nghóa laø ñoà thò voâ höôùng. Caùch töï nhieân ñeå veõ ñoà thò laø bieåu dieãn caùc ñænh baèng caùc ñieåm hoaëc voøng troøn, vaø caùc caïnh baèng caùc ñöôøng thaúng hoaëc caùc cung noái caùc ñænh. Ñoái vôùi ñoà thò coù höôùng thì caùc ñöôøng thaúng hay caùc cung caàn coù muõi teân chæ höôùng. Hình 13.1 minh hoïa moät soá ví duï veà ñoà thò. Ñoà thò thöù nhaát trong hình 13.1 coù caùc thaønh phoá laø caùc ñænh, vaø caùc tuyeán bay laø caùc caïnh. Trong ñoà thò thöù hai, caùc nguyeân töû hydro vaø carbon laø caùc ñænh, caùc lieân keát hoùa hoïc laø caùc caïnh. Hình thöù ba laø moät ñoà thò coù höôùng cho bieát khaû naêng truyeàn nhaän döõ lieäu treân maïng, caùc nuùt cuûa maïng (A, B, …, F) laø caùc ñænh vaø caùc ñöôøng noái caùc nuùt laø coù höôùng. Ñoâi khi caùch choïn taäp ñænh vaø taäp caïnh cho ñoà thò phuï thuoäc vaøo giaûi thuaät maø chuùng ta duøng ñeå giaûi baøi toaùn, chaúng haïn baøi toaùn lieân quan ñeán quy trình coâng vieäc, baøi toaùn xeáp thôøi khoùa bieåu,… Ñoà thò ñöôïc söû duïng ñeå moâ hình hoùa raát nhieàu daïng quaù trình cuõng nhö caáu truùc khaùc nhau. Ñoà thò coù theå bieåu dieãn maïng giao thoâng giöõa caùc thaønh phoá, hoaëc caùc thaønh phaàn cuûa moät maïch in ñieän töû vaø caùc ñöôøng noái giöõa chuùng, hoaëc caáu truùc cuûa moät phaân töû goàm caùc nguyeân töû vaø caùc lieân keát hoùa hoïc. Nhöõng ngöôøi daân trong moät thaønh phoá cuõng coù theå ñöôïc bieåu dieãn bôûi caùc ñænh cuûa ñoà thò maø caùc caïnh laø caùc moái quan heä giöõa hoï. Nhaân vieân trong moät coâng ty coù theå ñöôïc bieåu dieãn trong moät ñoà thò coù höôùng maø caùc caïnh coù höôùng cho bieát moái quan heä cuûa hoï vôùi nhöõng ngöôøi quaûn lyù. Nhöõng ngöôøi naøy cuõng coù theå coù nhöõng moái quan heä “cuøng laøm vieäc” bieåu dieãn bôûi caùc caïnh khoâng höôùng trong moät ñoà thò voâ höôùng. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 339
- Chöông 13 – Ñoà thò Hình 13.1 – Caùc ví duï veà ñoà thò 13.1.2. Ñoà thò voâ höôùng Moät vaøi daïng cuûa ñoà thò voâ höôùng ñöôïc minh hoïa trong hình 13.2. Hai ñænh trong moät ñoà thò voâ höôùng ñöôïc goïi laø keà nhau (adjacent) neáu toàn taïi moät caïnh noái töø ñænh naøy ñeán ñænh kia. Trong ñoà thò voâ höôùng trong hình 13.2 a, ñænh 1 vaø 2 laø keà nhau, ñænh 3 vaø 4 laø keà nhau, nhöng ñænh 1 vaø ñænh 4 khoâng keà nhau. Moät ñöôøng ñi (path) laø moät daõy caùc ñænh khaùc nhau, trong ñoù moãi ñænh keà vôùi ñænh keá tieáp. Hình (b) cho thaáy moät ñöôøng ñi. Moät chu trình (cycle) laø moät ñöôøng ñi chöùa ít nhaát ba ñænh sao cho ñænh cuoái cuøng keà vôùi ñænh ñaàu tieân. Hình (c) laø moät chu trình. Moät ñoà thò ñöôïc goïi laø lieân thoâng (connected) neáu luoân coù moät ñöôøng ñi töø moät ñænh baát kyø ñeán moät ñænh baát kyø naøo khaùc. Hình (a), (b), vaø (c) laø caùc ñoà thò lieân thoâng. Hình (d) khoâng phaûi laø ñoà thò lieân thoâng. Neáu moät ñoà thò laø khoâng lieân thoâng, chuùng ta xem moãi taäp con lôùn nhaát caùc ñænh lieân thoâng nhau nhö moät thaønh phaàn lieân thoâng. Ví duï, ñoà thò khoâng lieân thoâng ôû hình (d) coù hai thaønh phaàn lieân thoâng: moät thaønh phaàn chöùa caùc ñænh 1,2 vaø 4; moät thaønh phaàn chæ coù ñænh 3. Hình 13.2 – Caùc daïng cuûa ñoà thò voâ höôùng Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 340
- Chöông 13 – Ñoà thò Phaàn (e) laø moät ñoà thò lieân thoâng khoâng coù chu trình. Chuùng ta coù theå nhaän thaáy ñoà thò cuoái cuøng naøy thöïc söï laø moät caây, vaø chuùng ta duøng ñaëc tính naøy ñeå ñònh nghóa: Moät caây töï do (free tree) ñöôïc ñònh nghóa laø moät ñoà thò voâ höôùng lieân thoâng khoâng coù chu trình. 13.1.3. Ñoà thò coù höôùng Ñoái vôùi caùc ñoà thò coù höôùng, chuùng ta coù theå coù nhöõng ñònh nghóa töông töï. Chuùng ta yeâu caàu moïi caïnh trong moät ñöôøng ñi hoaëc moät chu trình ñeàu coù cuøng höôùng, nhö vaäy vieäc laàn theo moät ñöôøng ñi hoaëc moät chu trình coù nghóa laø phaûi di chuyeån theo höôùng chæ bôûi caùc muõi teân. Nhöõng ñöôøng ñi (hay chu trình) nhö vaäy ñöôïc goïi laø ñöôøng ñi coù höôùng (hay chu trình coù höôùng). Moät ñoà thò coù höôùng ñöôïc goïi laø lieân thoâng maïnh (strongly connected) neáu noù luoân coù moät ñöôøng ñi coù höôùng töø moät ñænh baát kyø ñeán moät ñænh baát kyø naøo khaùc. Trong moät ñoà thò coù höôùng khoâng lieân thoâng maïnh, neáu boû qua chieàu cuûa caùc caïnh maø chuùng ta coù ñöôïc moät ñoà thò voâ höôùng lieân thoâng thì ñoà thò coù höôùng ban ñaàu ñöôïc goïi laø ñoà thò lieân thoâng yeáu (weakly connected). Hình 13.3 minh hoïa moät chu trình coù höôùng, moät ñoà thò coù höôùng lieân thoâng maïnh vaø moät ñoà thò coù höôùng lieân thoâng yeáu. Hình 13.3 – Caùc ví duï veà ñoà thò coù höôùng Caùc ñoà thò coù höôùng trong phaàn (b) vaø (c) hình 13.3 coù caùc caëp ñænh coù caùc caïnh coù höôùng theo caû hai chieàu giöõa chuùng. Caùc caïnh coù höôùng laø caùc caëp coù thöù töï vaø caùc caëp coù thöù töï (ν, µ) vaø (µ,ν) laø khaùc nhau neáu ν ≠ µ. Trong ñoà thò voâ höôùng, chæ coù theå coù nhieàu nhaát moät caïnh noái hai ñænh khaùc nhau. Töông töï, do caùc ñænh treân moät caïnh theo ñònh nghóa laø phaûi khaùc nhau, khoâng theå coù moät caïnh noái moät ñænh vôùi chính noù. Tuy nhieân, cuõng coù nhöõng tröôøng hôïp môû roäng ñònh nghóa, ngöôøi ta cho pheùp nhieàu caïnh noái moät caëp ñænh, vaø moät caïnh noái moät ñænh vôùi chính noù. 13.2. Bieåu dieãn baèng maùy tính Neáu chuùng ta chuaån bò vieát chöông trình ñeå giaûi quyeát moät baøi toaùn coù lieân quan ñeán ñoà thò, tröôùc heát chuùng ta phaûi tìm caùch ñeå bieåu dieãn caáu truùc toaùn hoïc cuûa ñoà thò nhö laø moät daïng naøo ñoù cuûa caáu truùc döõ lieäu. Coù nhieàu phöông phaùp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 341
- Chöông 13 – Ñoà thò ñöôïc duøng phoå bieán, veà cô baûn chuùng khaùc nhau trong vieäc löïa choïn kieåu döõ lieäu tröøu töôïng ñeå bieåu dieãn ñoà thò, cuõng nhö nhieàu caùch hieän thöïc khaùc nhau cho moãi kieåu döõ lieäu tröøu töôïng. Noùi caùch khaùc, chuùng ta baét ñaàu töø moät ñònh nghóa toaùn hoïc, ñoù laø ñoà thò, sau ñoù chuùng ta tìm hieåu caùch moâ taû noù nhö moät kieåu döõ lieäu tröøu töôïng (taäp hôïp, baûng, hay danh saùch ñeàu coù theå duøng ñöôïc), vaø cuoái cuøng chuùng ta löïa choïn caùch hieän thöïc cho kieåu döõ lieäu tröøu töôïng maø chuùng ta choïn. 13.2.1. Bieåu dieãn cuûa taäp hôïp Ñoà thò ñöôïc ñònh nghóa baèng moät taäp hôïp, nhö vaäy moät caùch heát söùc töï nhieân laø duøng taäp hôïp ñeå xaùc ñònh caùch bieåu dieãn noù nhö laø döõ lieäu. Tröôùc tieân, chuùng ta coù moät taäp caùc ñænh, vaø thöù hai, chuùng ta coù caùc caïnh nhö laø taäp caùc caëp ñænh. Thay vì thöû bieåu dieãn taäp caùc caëp ñænh naøy moät caùch tröïc tieáp, chuùng ta chia noù ra thaønh nhieàu phaàn nhoû baèng caùch xem xeùt taäp caùc caïnh lieân quan ñeán töøng ñænh rieâng reõ. Noùi moät caùch khaùc, chuùng ta coù theå bieát ñöôïc taát caû caùc caïnh trong ñoà thò baèng caùch naém giöõ taäp Eν caùc caïnh coù chöùa ν ñoái vôùi moãi ñænh ν trong ñoà thò, hoaëc, moät caùch töông ñöông, taäp Aν goàm taát caû caùc ñænh keà vôùi ν. Thaät vaäy, chuùng ta coù theå duøng yù töôûng naøy ñeå ñöa ra moät ñònh nghóa môùi töông ñöông cho ñoà thò: Ñònh nghóa: Moät ñoà thò coù höôùng G bao goàm taäp V, goïi laø caùc ñænh cuûa G, vaø, ñoái vôùi moïi ν ∈ V, coù moät taäp con Aν , goïi laø taäp caùc ñænh keà cuûa ν. Töø caùc taäp con Aν chuùng ta coù theå taùi taïo laïi caùc caïnh nhö laø caùc caëp coù thöù töï theo quy taéc sau: caëp (ν, w) laø moät caïnh neáu vaø chæ neáu w∈ Aν. Xöû lyù cho taäp caùc ñænh deã hôn laø taäp caùc caïnh. Ngoaøi ra, ñònh nghóa môùi naøy thích hôïp vôùi caû ñoà thò coù höôùng vaø ñoà thò voâ höôùng. Moät ñoà thò laø voâ höôùng khi noù thoûa tính chaát ñoái xöùng sau: w∈ Aν keùo theo ν∈ Aw vôùi moïi ν, w∈V. Tính chaát naøy coù theå ñöôïc phaùt bieåu laïi nhö sau: Moät caïnh khoâng coù höôùng giöõa ν vaø w coù theå ñöôïc xem nhö hai caïnh coù höôùng, moät töø ν ñeán w vaø moät töø w ñeán ν. 13.2.1.1. Hieän thöïc caùc taäp hôïp Coù nhieàu caùch ñeå hieän thöïc taäp caùc ñænh trong caáu truùc döõ lieäu vaø giaûi thuaät. Caùch thöù nhaát laø bieåu dieãn taäp caùc ñænh nhö laø moät danh saùch caùc phaàn töû cuûa noù, chuùng ta seõ tìm hieåu phöông phaùp naøy sau. Caùch thöù hai, thöôøng goïi laø chuoãi caùc bit (bit string), löu moät trò Boolean cho moãi phaàn töû cuûa taäp hôïp ñeå chæ ra raèng noù coù hay khoâng coù trong taäp hôïp. Ñeå ñôn giaûn, chuùng ta seõ xem caùc phaàn töû coù theå coù cuûa taäp hôïp ñöôïc ñaùnh chæ soá töø 0 ñeán max_set-1, vôùi max_set laø soá phaàn töû toái ña cho pheùp. Ñieàu naøy coù theå ñöôïc hieän thöïc moät caùch deã daøng baèng caùch söû duïng thö vieän chuaån (Standard Template Library- STL) Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 342
- Chöông 13 – Ñoà thò std::bitset, hoaëc lôùp coù söû duïng template cho kích thöôùc taäp hôïp cuûa chuùng ta nhö sau: template struct Set { bool is_element[max_set]; }; Ñaây chæ laø moät caùch hieän thöïc ñôn giaûn nhaát cuûa khaùi nieäm taäp hôïp. Sinh vieân coù theå thaáy raèng khoâng coù gì ngaên caûn chuùng ta ñaëc taû vaø hieän thöïc moät CTDL taäp hôïp vôùi caùc phöông thöùc hoäi, giao, hieäu, xeùt thaønh vieân cuûa noù,…, moät caùch hoaøn chænh neáu nhö caàn söû duïng taäp hôïp trong nhöõng baøi toaùn lôùn naøo ñoù. Giôø chuùng ta ñaõ coù theå ñaëc taû caùch bieåu dieãn thöù nhaát cho ñoà thò cuûa chuùng ta: // Töông öùng hình 13.4-b template class Digraph { int count; // Soá ñænh cuûa ñoà thò, nhieàu nhaát laø max_size Set neighbors[max_size]; }; Trong caùch hieän thöïc naøy, caùc ñænh ñöôïc ñaët teân baèng caùc soá nguyeân töø 0 ñeán count-1. Neáu ν laø moät soá nguyeân thì phaàn töû neighbors[ν] cuûa maûng laø moät taäp caùc ñænh keà vôùi ñænh ν. 13.2.1.2. Baûng keà Trong caùch hieän thöïc treân ñaây, caáu truùc Set ñöôïc hieän thöïc nhö moät maûng caùc phaàn töû kieåu bool. Moãi phaàn töû chæ ra raèng ñænh töông öùng coù laø thaønh phaàn cuûa taäp hôïp hay khoâng. Neáu chuùng ta thay theá taäp caùc ñænh keà naøy baèng moät maûng, chuùng ta seõ thaáy raèng maûng neighbors trong ñònh nghóa cuûa lôùp Graph coù theå ñöôïc bieán ñoåi thaønh maûng caùc maûng (maûng hai chieàu) nhö sau ñaây, vaø chuùng ta goïi laø baûng keà (adjacency table): // Töông öùng hình 13.4-c template class Digraph { int count; // Soá ñænh cuûa ñoà thò, nhieàu nhaát laø max_size. bool adjacency[max_size][max_size]; }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 343
- Chöông 13 – Ñoà thò Baûng keà chöùa caùc thoâng tin moät caùch töï nhieân nhö sau: adjacency[v][w] laø true neáu vaø chæ neáu ñænh v laø ñænh keà cuûa w. Neáu laø ñoà thò coù höôùng, adjacency[v][w] cho bieát caïnh töø v ñeán w coù trong ñoà thò hay khoâng. Neáu ñoà thò voâ höôùng, baûng keà phaûi ñoái xöùng, nghóa laø adjacency[v][w]= adjacency[v][w] vôùi moïi v vaø w. Bieåu dieãn ñoà thò bôûi taäp caùc ñænh keà vaø bôûi baûng keà ñöôïc minh hoïa trong hình 13.4. (a) (b) (c) Hình 13.4 – Taäp caùc ñænh keà vaø baûng keà. 13.2.2. Danh saùch keà Moät caùch khaùc ñeå bieåu dieãn moät taäp hôïp laø duøng danh saùch caùc phaàn töû. Chuùng ta coù moät danh saùch caùc ñænh, vaø, ñoái vôùi moãi ñænh, coù moät danh saùch caùc ñænh keà. Chuùng ta coù theå xem xeùt caùch hieän thöïc cho ñoà thò baèng danh saùch lieân tuïc hoaëc danh saùch lieân keát ñôn. Tuy nhieân, ñoái vôùi nhieàu öùng duïng, ngöôøi ta thöôøng söû duïng caùc hieän thöïc khaùc cuûa danh saùch phöùc taïp hôn nhö caây nhò phaân tìm kieám, caây nhieàu nhaùnh tìm kieám, hoaëc laø heap. Löu yù raèng, baèng caùch ñaët teân caùc ñænh theo caùc chæ soá trong caùc caùch hieän thöïc tröôùc ñaây, chuùng ta cuõng coù ñöôïc caùch hieän thöïc cho taäp caùc ñænh nhö laø moät danh saùch lieân tuïc. 13.2.2.1. Hieän thöïc döïa treân cô sôû laø danh saùch Chuùng ta coù ñöôïc hieän thöïc cuûa ñoà thò döïa treân cô sôû laø danh saùch baèng caùch thay theá caùc taäp hôïp ñænh keà tröôùc kia baèng caùc danh saùch. Hieän thöïc naøy coù theå söû duïng hoaëc danh saùch lieân tuïc hoaëc danh saùch lieân keát. Phaàn (b) vaø (c) cuûa hình 13.5 minh hoïa hai caùch hieän thöïc naøy. // Toång quaùt cho caû danh saùch lieân tuïc laãn lieân keát (hình 13.5-b vaø c). typedef int Vertex; template class Digraph { int count; // Soá ñænh cuûa ñoà thò, nhieàu nhaát laø max_size. List neighbors[max_size]; }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 344
- Chöông 13 – Ñoà thò 13.2.2.2. Hieän thöïc lieân keát Baèng caùch söû duïng caùc ñoái töôïng lieân keát cho caû caùc ñænh vaø cho caû caùc danh saùch keà, ñoà thò seõ coù ñöôïc tính linh hoaït cao nhaát. Hieän thöïc naøy ñöôïc minh hoïa trong hình 13.5-a vaø coù caùc ñònh nghóa nhö sau: Hình 13.5 – Hieän thöïc ñoà thò baèng caùc danh saùch class Edge; class Vertex { Edge *first_edge; // Chæ ñeán phaàn töû ñaàu cuûa DSLK caùc ñænh keà. Vertex *next_vertex; // Chæ ñeán phaàn töû keá trong DSLK caùc ñænh coù trong ñoà thò. }; class Edge { Vertex *end_point; // Chæ ñeán moät ñænh keà vôùi ñænh maø danh saùch naøy thuoäc veà. Edge *next_edge; // Chæ ñeán phaàn töû bieåu dieãn ñænh keà keá tieáp trong danh saùch caùc ñænh keà vôùi moät ñænh maø danh saùch naøy thuoäc veà. }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 345
- Chöông 13 – Ñoà thò class Digraph { Vertex *first_vertex;// Chæ ñeán phaàn töû ñaàu tieân trong danh saùch caùc ñænh cuûa ñoà thò. }; 13.2.3. Caùc thoâng tin khaùc trong ñoà thò Nhieàu öùng duïng veà ñoà thò khoâng nhöõng caàn nhöõng thoâng tin veà caùc ñænh keà cuûa moät ñænh maø coøn caàn theâm moät soá thoâng tin khaùc lieân quan ñeán caùc ñænh cuõng nhö caùc caïnh. Trong hieän thöïc lieân keát, caùc thoâng tin naøy coù theå ñöôïc löu nhö caùc thuoäc tính boå sung beân trong caùc baûn ghi töông öùng, vaø trong hieän thöïc lieân tuïc, chuùng coù theå ñöôïc löu trong caùc maûng caùc phaàn töû beân trong caùc baûn ghi. Laáy ví duï tröôøng hôïp maïng caùc maùy tính, noù ñöôïc ñònh nghóa nhö moät ñoà thò trong ñoù moãi caïnh coù theâm thoâng tin laø taûi troïng cuûa ñöôøng truyeàn töø maùy naøy qua maùy khaùc. Ñoái vôùi nhieàu giaûi thuaät treân maïng, caùch bieåu dieãn toát nhaát laø duøng baûng keà, trong ñoù caùc phaàn töû seõ chöùa taûi troïng thay vì moät trò kieåu bool. Chuùng ta seõ quay laïi vaán ñeà naøy sau trong chöông naøy. 13.3. Duyeät ñoà thò 13.3.1. Caùc phöông phaùp Trong nhieàu baøi toaùn, chuùng ta mong muoán ñöôïc khaûo saùt caùc ñænh trong ñoà thò theo moät thöù töï naøo ñoù. Töïa nhö ñoái vôùi caây nhò phaân chuùng ta ñaõ phaùt trieån moät vaøi phöông phaùp duyeät qua caùc phaàn töû moät caùch coù heä thoáng. Khi duyeät caây, chuùng ta thöôøng baét ñaàu töø nuùt goác. Trong ñoà thò, thöôøng khoâng coù ñænh naøo laø ñænh ñaëc bieät, neân vieäc duyeät qua ñoà thò coù theå baét ñaàu töø moät ñænh baát kyø naøo ñoù. Tuy coù nhieàu thöù töï khaùc nhau ñeå duyeät qua caùc ñænh cuûa ñoà thò, coù hai phöông phaùp ñöôïc xem laø ñaëc bieät quan troïng. Phöông phaùp duyeät theo chieàu saâu (depth-first traversal) treân moät ñoà thò gaàn gioáng vôùi pheùp duyeät preorder cho moät caây coù thöù töï. Giaû söû nhö pheùp duyeät vöøa duyeät xong ñænh ν, vaø goïi w1, w2,...,wk laø caùc ñænh keà vôùi ν, thì w1 laø ñænh ñöôïc duyeät keá tieáp, trong khi caùc ñænh w2,...,wk seõ naèm ñôïi. Sau khi duyeät qua ñænh w1 chuùng ta seõ duyeät qua taát caû caùc ñænh keà vôùi w1, tröôùc khi quay laïi vôùi w2,...,wk. Phöông phaùp duyeät theo chieàu roäng (breadth-first traversal) treân moät ñoà thò gaàn gioáng vôùi pheùp duyeät theo möùc (level by level) cho moät caây coù thöù töï. Neáu pheùp duyeät vöøa duyeät xong ñænh ν, thì taát caû caùc ñænh keà vôùi ν seõ ñöôïc duyeät tieáp sau ñoù, trong khi caùc ñænh keà vôùi caùc ñænh naøy seõ ñöôïc ñaët vaøo moät danh saùch chôø, chuùng seõ ñöôïc duyeät tôùi chæ sau khi taát caû caùc ñænh keà vôùi ν ñaõ ñöôïc duyeät xong. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 346
- Chöông 13 – Ñoà thò Hình 13.6 minh hoïa hai phöông phaùp duyeät treân, caùc con soá taïi caùc ñænh bieåu dieãn thöù töï maø chuùng ñöôïc duyeät ñeán. Hình 13.6 - Duyeät ñoà thò 13.3.2. Giaûi thuaät duyeät theo chieàu saâu Phöông phaùp duyeät theo chieàu saâu thöôøng ñöôïc xaây döïng nhö moät giaûi thuaät ñeä quy. Caùc coâng vieäc caàn laøm khi gaëp moät ñænh ν laø: visit(v); for (moãi ñænh w keà vôùi ñænh v) traverse(w); Tuy nhieân, trong pheùp duyeät ñoà thò, coù hai ñieåm khoù khaên maø trong pheùp duyeät caây khoâng coù. Thöù nhaát, ñoà thò coù theå chöùa chu trình, vaø giaûi thuaät cuûa chuùng ta coù theå gaëp laïi moät ñænh laàn thöù hai. Ñeå ngaên chaën ñeä quy voâ taän, chuùng ta duøng moät maûng caùc phaàn töû kieåu bool visited, visited[v] seõ laø true khi v vöøa ñöôïc duyeät xong, vaø chuùng ta luoân xeùt trò cuûa visited[w] tröôùc khi xöû lyù cho w, neáu trò naøy ñaõ laø true thì w khoâng caàn xöû lyù nöõa. Ñieàu khoù khaên thöù hai laø, ñoà thò coù theå khoâng lieân thoâng, vaø giaûi thuaät duyeät coù theå khoâng ñaït ñöôïc ñeán taát caû caùc ñænh cuûa ñoà thò neáu chæ baét ñaàu ñi töø moät ñænh. Do ñoù chuùng ta caàn thöïc hieän moät voøng laëp ñeå coù theå baét ñaàu töø moïi ñænh trong ñoà thò, nhôø vaäy chuùng ta seõ khoâng boû soùt moät ñænh naøo. Vôùi nhöõng phaân tích treân, chuùng ta coù phaùc thaûo cuûa giaûi thuaät duyeät ñoà thò theo chieàu saâu döôùi ñaây. Chi tieát hôn cho giaûi thuaät coøn phuï thuoäc vaøo caùch choïn löïa hieän thöïc cuûa ñoà thò vaø caùc ñænh, vaø chuùng ta ñeå laïi cho caùc chöông trình öùng duïng. template void Digraph::depth_first(void (*visit)(Vertex &)) const /* post: Haøm *visit ñöôïc thöïc hieän taïi moãi ñænh cuûa ñoà thò moät laàn, theo thöù töï duyeät theo chieàu saâu. uses: Haøm traverse thöïc hieän duyeät theo chieàu saâu. */ Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 347
- Chöông 13 – Ñoà thò { bool visited[max_size]; Vertex v; for (all v in G) visited[v] = false; for (all v in G) if (!visited[v]) traverse(v, visited, visit); } Vieäc ñeä quy ñöôïc thöïc hieän trong haøm phuï trôï traverse. Do haøm naøy caàn truy nhaäp vaøo caáu truùc beân trong cuûa ñoà thò, noù phaûi laø haøm thaønh vieân cuûa lôùp Digraph. Ngoaøi ra, do traverse laø moät haøm phuï trôï vaø chæ ñöôïc söû duïng trong phöông thöùc depth_first, noù neân ñöôïc khai baùo private beân trong lôùp. template void Digraph::traverse(Vertex &v, bool visited[], void (*visit)(Vertex &)) const /* pre: v laø moät ñænh cuûa ñoà thò Digraph. post: Duyeät theo chieàu saâu, haøm *visit seõ ñöôïc thöïc hieän taïi v vaø taïi taát caû caùc ñænh coù theå ñeán ñöôïc töø v. uses: Haøm traverse moät caùch ñeä quy. */ { Vertex w; visited[v] = true; (*visit)(v); for (all w adjacent to v) if (!visited[w]) traverse(w, visited, visit); } 13.3.3. Giaûi thuaät duyeät theo chieàu roäng Do söû duïng ñeä quy vaø laäp trình vôùi ngaên xeáp veà baûn chaát laø töông ñöông, chuùng ta coù theå xaây döïng giaûi thuaät duyeät theo chieàu saâu baèng caùch söû duïng ngaên xeáp. Khi moät ñænh ñang ñöôïc duyeät thì caùc ñænh keà cuûa noù ñöôïc ñaåy vaøo ngaên xeáp, khi moät ñænh vöøa ñöôïc duyeät xong thì ñænh keá tieáp caàn duyeät laø ñænh ñöôïc laáy ra töø ngaên xeáp. Giaûi thuaät duyeät theo chieàu roäng cuõng töông töï nhö giaûi thuaät vöøa ñöôïc ñeà caäp ñeán trong vieäc duyeät theo chieàu saâu, tuy nhieân haøng ñôïi caàn ñöôïc söû duïng thay cho ngaên xeáp. template void Digraph::breadth_first(void (*visit)(Vertex &)) const /* post: Haøm *visit ñöôïc thöïc hieän taïi moãi ñænh cuûa ñoà thò moät laàn, theo thöù töï duyeät theo chieàu roäng. uses: Caùc phöông thöùc cuûa lôùp Queue. */ { Queue q; bool visited[max_size]; Vertex v, w, x; for (all v in G) visited[v] = false; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 348
- Chöông 13 – Ñoà thò for (all v in G) if (!visited[v]) { q.append(v); while (!q.empty()){ q.retrieve(w); if (!visited[w]) { visited[w] = true; (*visit)(w); for (all x adjacent to w) q.append(x); } q.serve(); } } } 13.4. Saép thöù töï topo 13.4.1. Ñaët vaán ñeà Neáu G laø moät ñoà thò coù höôùng khoâng coù chu trình, thì thöù töï topo (topological order) cuûa G laø moät caùch lieät keâ tuaàn töï moïi ñænh trong G sao cho, vôùi moïi ν, µ∈G, neáu coù moät caïnh töø ν ñeán µ, thì ν naèm tröôùc µ. Trong suoát phaàn naøy, chuùng seõ chæ xem xeùt caùc ñoà thò coù höôùng khoâng coù chu trình. Thuaät ngöõ acyclic coù nghóa laø moät ñoà thò khoâng coù chu trình. Caùc ñoà thò nhö vaäy xuaát hieän trong raát nhieàu baøi toaùn. Nhö moät ví duï ñaàu tieân veà thöù töï topo, chuùng ta haõy xem xeùt caùc moân hoïc trong moät tröôøng ñaïi hoïc nhö laø caùc ñænh cuûa ñoà thò, trong ñoù moät caïnh noái töø moân naøy ñeán moân kia coù nghóa laø moân thöù nhaát laø moân tieân quyeát cuûa moân thöù hai. Nhö vaäy thöù töï topo seõ lieät keâ taát caû caùc moân sao cho moïi moân tieân quyeát cuûa moät moân seõ naèm tröôùc moân ñoù. Ví duï thöù hai laø töø ñieån caùc thuaät ngöõ kyõ thuaät. Caùc töø trong töø ñieån ñöôïc saép thöù töï sao cho khoâng coù töø naøo ñöôïc söû duïng trong moät ñònh nghóa cuûa töø khaùc tröôùc khi chính noù ñöôïc ñònh nghóa. Töông töï, caùc taùc giaû cuûa caùc saùch söû duïng thöù töï topo cho caùc ñeà muïc trong saùch. Hai thöù töï topo khaùc nhau cuûa moät ñoà thò coù höôùng ñöôïc minh hoïa trong hình 13.7. Chuùng ta seõ xaây döïng haøm ñeå sinh ra thöù töï topo cho caùc ñænh cuûa moät ñoà thò khoâng coù chu trình theo hai caùch: söû duïng pheùp duyeät theo chieàu saâu vaø pheùp duyeät theo chieàu roäng. Caû hai phöông phaùp ñöôïc duøng cho moät ñoái töôïng cuûa lôùp Digraph söû duïng hieän thöïc döïa treân cô sôû laø danh saùch. Chuùng ta coù ñaëc taû lôùp nhö sau: typedef int Vertex; template class Digraph { public: Digraph(); void read(); void write(); Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 349
- Chöông 13 – Ñoà thò // Caùc phöông thöùc saép thöù töï topo. void depth_sort(List &topological_order); void breadth_sort(List &topological_order); private: int count; List neighbors[graph_size]; void recursive_depth_sort(Vertex v, bool visited[], List &topological_order); }; Haøm phuï trôï recursive_depth_sort ñöôïc söû duïng bôûi phöông thöùc depth_sort. Caû hai phöông phaùp saép thöù töï ñeàu seõ taïo ra moät danh saùch caùc ñænh cuûa ñoà thò theo thöù töï topo töông öùng. Hình 13.7 – Caùc thöù tö topo cuûa moät ñoà thò coù höôùng 13.4.2. Giaûi thuaät duyeät theo chieàu saâu Trong thöù töï topo, moãi ñænh phaûi xuaát hieän tröôùc moïi ñænh keà cuûa noù trong ñoà thò. Giaûi thuaät duyeät theo chieàu saâu naøy ñaët daàn caùc ñænh vaøo maûng thöù töï topo töø phaûi sang traùi. Baét ñaàu töø moät ñænh chöa töøng ñöôïc duyeät ñeán, chuùng ta caàn goïi ñeä quy ñeå ñeán ñöôïc caùc ñænh maø khoâng coøn ñænh keà, caùc ñænh naøy seõ ñöôïc ñaët vaøo maûng thöù töï topo ôû caùc vò trí cuoái maûng. Tính töø phaûi sang traùi trong maûng thöù töï topo naøy, khi caùc ñænh keà cuûa moät ñænh ñaõ ñöôïc duyeät xong, thì chính ñænh ñoù Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 350
- Chöông 13 – Ñoà thò coù theå coù maët trong maûng. Ñoù chính laø luùc caùc laàn goïi ñeä quy beân trong luøi veà laàn goïi ñeä quy beân ngoaøi. Phöông phaùp naøy laø moät caùch hieän thöïc tröïc tieáp cuûa thuû tuïc duyeät theo chieàu saâu moät caùch toång quaùt ñaõ ñöôïc trình baøy ôû treân. Ñieåm khaùc bieät laø vieäc xöû lyù taïi moãi ñænh (ghi vaøo maûng thöù töï topo) chæ ñöôïc thöïc hieän sau khi caùc ñænh keà cuûa noù ñaõ ñöôïc xöû lyù. template void Digraph::depth_sort(List &topological_order) /* post: Caùc ñænh cuûa moät ñoà thò coù höôùng khoâng coù chu trình ñöôïc xeáp theo thöù töï topo töông öùng caùch duyeät ñoà thò theo chieàu saâu. uses: Caùc phöong thöùc cuûa lôùp List, haøm ñeä quy recursive_depth_sort. */ { bool visited[graph_size]; Vertex v; for (v = 0; v < count; v++) visited[v] = false; topological_order.clear(); for (v = 0; v < count; v++) if (!visited[v]) // Theâm caùc ñænh keà cuûa v vaø sau ñoù laø v vaøo maûng töù töï topo töø phaûi sang traùi. recursive_depth_sort(v, visited, topological_order); } Haøm phuï trôï recursive_depth_sort thöïc hieän vieäc ñeä quy, döïa treân phaùc thaûo cuûa haøm traverse toång quaùt, tröôùc heát ñaët taát caû caùc ñænh sau cuûa moät ñænh v vaøo caùc vò trí cuûa chuùng trong thöù töï topo, sau ñoù môùi ñaët v vaøo. template void Digraph::recursive_depth_sort(Vertex v, bool *visited, List &topological_order) /* pre: Ñænh v chöa coù trong maûng thöù töï topo. post: Theâm caùc ñænh keà cuûa v vaø sau ñoù laø v vaøo maûng töù töï topo töø phaûi sang traùi. uses: Caùc phöông thöùc cuûa lôùp List vaø haøm ñeä quy recursive_depth_sort. */ { visited[v] = true; int degree = neighbors[v].size(); for (int i = 0; i < degree; i++) { Vertex w; neighbors[v].retrieve(i, w); // Moät ñænh keà cuûa v. if (!visited[w]) // Duyeät tieáp xuoáng ñænh w. recursive_depth_sort(w, visited, topological_order); } topological_order.insert(0, v); // Ñaët v vaøo maûng thöù töï topo. } Do giaûi thuaät naøy duyeät qua moãi ñænh cuûa ñoà thò chính xaùc moät laàn vaø xem xeùt moãi caïnh cuõng moät laàn, ñoàng thôøi noù khoâng heà thöïc hieän vieäc tìm kieám naøo, neân thôøi gian chaïy laø O(n+e), vôùi n laø soá ñænh vaø e laø soá caïnh cuûa ñoà thò. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 351
- Chöông 13 – Ñoà thò 13.4.3. Giaûi thuaät duyeät theo chieàu roäng Trong thöù töï topo theo chieàu roäng cuûa moät ñoà thò coù höôùng khoâng coù chu trình, chuùng ta baét ñaàu baèng caùch tìm caùc ñænh coù theå laø caùc ñænh ñaàu tieân trong thöù töï topo vaø sau ñoù chuùng ta aùp duïng nguyeân taéc raèng, moïi ñænh caàn phaûi xuaát hieän tröôùc taát caû caùc ñænh sau cuûa noù trong thöù töï topo. Giaûi thuaät naøy seõ laàn löôït ñaët caùc ñænh cuûa ñoà thò vaøo maûng thöù töï topo töø traùi sang phaûi. Caùc ñænh coù theå laø ñænh ñaàu tieân chính laø caùc ñænh khoâng laø ñænh sau cuûa baát kyø ñænh naøo trong ñoà thò. Ñeå tìm ñöôïc chuùng, chuùng ta taïo moät maûng predecessor_count, moãi phaàn töû taïi chæ soá v chöùa soá ñænh ñöùng ngay tröôùc ñænh v. Caùc ñænh caàn tìm chính laø caùc ñænh maø khoâng coù ñænh naøo ñöùng ngay tröôùc noù, trò trong phaàn töû töông öùng cuûa maûng baèng 0. Caùc ñænh nhö vaäy ñaõ saün saøng ñöôïc ñaët vaøo maûng thöù tö topo. Nhö vaäy chuùng ta seõ khôûi ñoäng quaù trình duyeäït theo chieàu roäng baèng caùch ñaët caùc ñænh naøy vaøo moät haøng caùc ñænh seõ ñöôïc xöû lyù. Khi moät ñænh caàn ñöôïc xöû lyù, noù seõ ñöôïc laáy ra töø haøng vaø ñaët vaøo vò trí keá tieáp trong maûng topo, luùc naøy, vieäc xem xeùt noù xem nhö keát thuùc vaø ñöôïc ñaùnh daáu baèng caùch cho caùc phaàn töû trong maûng predecessor_count töông öùng vôùi caùc ñænh laø ñænh sau cuûa noù giaûm ñi 1. Khi moät phaàn töû naøo trong maûng naøy ñaït ñöôïc trò 0, thì cuõng coù nghóa laø ñænh töông öùng vôùi noù coù caùc ñænh tröôùc ñaõ ñöôïc duyeät xong, vaø ñænh naøy ñaõ saün saøng ñöôïc duyeät neân ñöôïc ñöa vaøo haøng ñôïi. template void Digraph::breadth_sort(List &topological_order) /* post: Caùc ñænh cuûa moät ñoà thò coù höôùng khoâng coù chu trình ñöôïc xeáp theo thöù töï topo töông öùng caùch duyeät ñoà thò theo chieàu roäng. uses: Caùc phöông thöùc cuûa caùc lôùp List, Queue. */ { topological_order.clear(); Vertex v, w; int predecessor_count[graph_size]; for (v = 0; v < count; v++) predecessor_count[v] = 0; for (v = 0; v < count; v++) for (int i = 0; i < neighbors[v].size(); i++) { // Caäp nhaät soá ñænh ñöùng tröôùc cho moãi ñænh. neighbors[v].retrieve(i, w); predecessor_count[w]++; } Queue ready_to_process; for (v = 0; v < count; v++) if (predecessor_count[v] == 0) ready_to_process.append(v); while (!ready_to_process.empty()) { ready_to_process.retrieve(v); topological_order.insert(topological_order.size(), v); for (int j = 0; j < neighbors[v].size(); j++) { // Giaûm soá ñænh ñöùng tröôùc neighbors[v].retrieve(j, w); // cuûa moãi ñænh keà cuûa v ñi 1 predecessor_count[w]--; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 352
- Chöông 13 – Ñoà thò if (predecessor_count[w] == 0) ready_to_process.append(w); } ready_to_process.serve(); } } Giaûi thuaät naøy caàn ñeán moät trong caùc hieän thöïc cuûa lôùp Queue. Queue coù theå coù hieän thöïc theo baát kyø caùch naøo ñaõ ñöôïc moâ taû trong chöông 3. Do caùc phaàn töû trong Queue laø caùc ñænh. Cuõng nhö duyeät theo chieàu saâu, thôøi gian caàn cho haøm breadth_first laø O(n+e), vôùi n laø soá ñænh vaø e laø soá caïnh cuûa ñoà thò. 13.5. Giaûi thuaät Greedy: Tìm ñöôøng ñi ngaén nhaát 13.5.1. Ñaët vaán ñeà Nhö moät öùng duïng khaùc cuûa ñoà thò, chuùng ta xem xeùt moät baøi toaùn hôi phöùc taïp sau ñaây. Chuùng ta coù moät ñoà thò coù höôùng G, trong ñoù moãi caïnh ñöôïc gaùn moät con soá khoâng aâm goïi laø taûi troïng (weight). Baøi toaùn cuûa chuùng ta laø tìm moät ñöôøng ñi töø moät ñænh ν ñeán moät ñænh w sao cho toång taûi troïng treân ñöôøng ñi laø nhoû nhaát. Chuùng ta goïi ñöôøng ñi nhö vaäy laø ñöôøng ñi ngaén nhaát (shortest path), maëc duø taûi troïng coù theå bieåu dieãn cho giaù caû, thôøi gian, hoaëc moät vaøi ñaïi löôïng naøo khaùc thay vì khoaûng caùch. Chuùng ta coù theå xem G nhö moät baûn ñoà caùc tuyeán bay, chaúng haïn, moãi ñænh cuûa ñoà thò bieåu dieãn moät thaønh phoá vaø taûi troïng treân moãi caïnh bieåu dieãn chi phí bay töø thaønh phoá naøy sang thaønh phoá kia. Baøi toaùn cuûa chuùng ta laø tìm loä trình bay töø thaønh phoá ν ñeán thaønh phoá w sao cho toång chi phí laø nhoû nhaát. Chuùng ta haõy xem xeùt ñoà thò ôû hình 13.8. Ñöôøng ngaén nhaát töø ñænh 0 ñeán ñænh 1 ñi ngang qua ñænh 2 coù toång taûi troïng laø 4, so vôùi taûi troïng laø 5 ñoái vôùi caïnh noái tröïc tieáp töø 0 sang 1, vaø toång taûi troïng laø 8 neáu ñi ngang qua ñænh 4. Hình 13.8 – Ñoà thò coù höôùng vôùi caùc taûi troïng Coù theå deã daøng giaûi baøi toaùn moät caùch toång quaùt nhö sau: baét ñaàu töø moät ñænh, goïi laø ñænh nguoàn, tìm ñöôøng ñi ngaén nhaát ñeán moïi ñænh coøn laïi, thay vì chæ tìm ñöôøng ñeán moät ñænh ñích. Chuùng ta caàn taûi troïng phaûi laø nhöõng soá khoâng aâm. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 353
- Chöông 13 – Ñoà thò 13.5.2. Phöông phaùp Giaûi thuaät seõ ñöôïc thöïc hieän baèng caùch naém giöõ moät taäp S caùc ñænh maø ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán chuùng ñaõ ñöôïc bieát. Môùi ñaàu, ñænh nguoàn laø ñænh duy nhaát trong S. Taïi moãi böôùc, chuùng ta theâm vaøo S caùc ñænh coøn laïi maø ñöôøng ñi ngaén nhaát töø nguoàn ñeán chuùng vöøa ñöôïc tìm thaáy. Baøi toaùn baây giôø trôû thaønh baøi toaùn xaùc ñònh ñænh naøo ñeå theâm vaøo S taïi moãi böôùc. Chuùng ta haõy xem nhöõng ñænh ñaõ coù trong S nhö ñaõ ñöôïc toâ moät maøu naøo ñoù, vaø caùc caïnh naèm trong caùc ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán caùc ñænh coù maøu cuõng ñöôïc toâ maøu. Chuùng ta seõ naém giöõ moät maûng distance cho bieát raèng, ñoái vôùi moãi ñænh ν, khoaûng caùch töø ñænh nguoàn doïc theo ñöôøng ñi coù caùc caïnh ñaõ coù maøu, coù theå tröø caïnh cuoái cuøng. Nghóa laø, neáu ν thuoäc S, thì distance[v] chöùa khoaûng caùch ngaén nhaát ñeán ν, vaø moïi caïnh naèm treân ñöôøng ñi töông öùng ñeàu coù maøu. Neáu ν khoâng thuoäc S, thì distance[v] chöùa chieàu daøi cuûa ñöôøng ñi töø ñænh nguoàn ñeán moät ñænh w naøo ñoù coäng vôùi taûi troïng cuûa caïnh noái töø w ñeán ν, vaø moïi caïnh naèm treân ñöôøng ñi naøy, tröø caïnh cuoái, ñeàu coù maøu. Maûng distance ñöôïc khôûi taïo baèng caùch gaùn töøng distance[v] vôùi trò cuûa taûi troïng cuûa caïnh noái töø ñænh nguoàn ñeán ν neáu toàn taïi caïnh naøy, ngöôïc laïi noù ñöôïc gaùn baèng voâ cöïc. Hình 13.9 – Tìm moät ñöôøng ñi ngaén Ñeå xaùc ñònh ñænh ñöôïc theâm vaøo S taïi moãi böôùc, chuùng ta aùp duïng moät “tieâu chí tham lam” (greedy criterion) trong vieäc choïn ra moät ñænh ν coù khoaûng caùch nhoû nhaát töø trong maûng distance sao cho ν chöa coù trong S. Chuùng ta caàn chöùng minh raèng, ñoái vôùi ñænh ν naøy, khoaûng caùch chöùa trong maûng distance thöïc söï laø chieàu daøi cuûa ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán ν. Giaû söû coù moät ñöôøng ñi ngaén hôn töø nguoàn ñeán ν, nhö hình 13.9. Ñöôøng ñi naøy ñi ngang moät ñænh x naøo ñoù chöa thuoäc S roài môùi ñeán ν (coù theå laïi qua moät soá ñænh khaùc coù naèm trong S tröôùc khi gaëp ν). Nhöng neáu ñöôøng ñi naøy ngaén hôn ñöôøng ñi ñaõ ñöôïc toâ maøu ñeán ν, thì ñoaïn ñöôøng ban ñaàu trong noù töø nguoàn ñeán x coøn ngaén hôn nöõa, nghóa laø distance[x] < distance[v], vaø nhö vaäy tieâu chí tham lam ñaõ phaûi choïn x thay vì ν laø ñænh keá tieáp ñöôïc theâm vaøo S. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 354
- Chöông 13 – Ñoà thò Khi theâm ν vaø S, chuùng ta seõ toâ maøu ν vaø toâ maøu luoân ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán ν (moïi caïnh trong noù tröø caïnh cuoái thöïc söï ñaõ ñöôïc toâ maøu tröôùc Hình 12.10 - Ví duï veà caùc ñöôøng ñi ngaén nhaát ñoù). Keá tieáp, chuùng ta caàn caäp nhaät laïi caùc phaàn töû cuûa maûng distance baèng caùch xem xeùt ñoái vôùi moãi ñænh w naèm ngoaøi S, ñöôøng ñi töø nguoàn qua ν roài ñeán w coù ngaén hôn khoaûng caùch töø nguoàn ñeán w ñaõ ñöôïc ghi nhaän tröôùc ñoù hay khoâng. Neáu ñieàu naøy xaûy ra coù nghóa laø chuùng ta vöøa phaùt hieän ñöôïc moät ñöôøng ñi môùi cho ñænh w coù ñi ngang qua ν ngaén hôn caùch ñi ñaõ xaùc ñònh tröôùc ñoù, vaø nhö vaäy chuùng ta caàn caäp nhaät laïi distance[w] baèng distance[v] coäng vôùi taûi troïng cuûa caïnh noái töø ν ñeán w. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 355
- Chöông 13 – Ñoà thò 13.5.3. Ví duï Tröôùc khi vieát moät haøm cho phöông phaùp naøy, chuùng ta haõy xem qua ví duï ôû hình 13.10. Ñoái vôùi ñoà thò coù höôùng ôû hình (a), traïng thaùi ban ñaàu ñöôïc chæ ra ôû hình (b): taäp S (caùc ñænh ñaõ ñöôïc toâ maøu) chæ goàm coù nguoàn laø ñænh 0, caùc phaàn töû cuûa maûng distance chöùa caùc con soá ñöôïc ñaët caïnh moãi ñænh coøn laïi. Khoaûng caùch ñeán ñænh 4 ngaén nhaát, neân 4 ñöôïc theâm vaøo S nhö ôû hình (c), vaø distance[3] ñöôïc caäp nhaät thaønh 6. Do khoaûng caùch ñeán 1 vaø 2 ngang qua 4 lôùn hôn khoaûng caùch ñaõ chöùa trong maûng distance, neân caùc khoaûng caùch naøy trong distance ñöôïc giöõ khoâng ñoåi. Ñænh keá tieáp gaàn nhaát ñoái vôùi nguoàn laø ñænh 2, noù ñöôïc theâm vaøo S nhö hình (d), khoaûng caùch ñeán caùc ñænh 1 vaø 3 ñöôïc caäp nhaät laïi ngang qua ñænh naøy. Hai böôùc cuoái cuøng, trong hình (e) vaø (f), ñænh 1 vaø 3 ñöôïc theâm vaøo vaø caùc ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán caùc ñænh coøn laïi ñöôïc chæ ra trong sô ñoà cuoái. 13.5.4. Hieän thöïc Ñeå hieän thöïc giaûi thuaät tìm ñöôøng ngaén nhaát treân, chuùng ta caàn choïn caùch hieän thöïc cho ñoà thò coù höôùng. Vieäc duøng baûng keà cho pheùp truy xuaát ngaãu nhieân ñeán moïi ñænh cuûa ñoà thò. Hôn nöõa, chuùng ta coù theå söû duïng baûng vöøa ñeå chöùa caùc taûi troïng vöøa ñeå chöùa thoâng tin veà caùc ñænh keà. Trong ñaëc taû döôùi ñaây cuûa ñoà thò coù höôùng, chuùng ta theâm thoâng soá template cho pheùp ngöôøi söû duïng choïn löïa kieåu cuûa taûi troïng theo yù muoán. Laáy ví duï, ngöôøi söû duïng khi duøng lôùp Digraph ñeå moâ hình hoùa maïng caùc tuyeán bay, hoï coù theå chöùa giaù veù laø moät soá nguyeân hay moät soá thöïc. template class Digraph { public: // Theâm constructor vaø caùc phöông thöùc nhaäp vaø xuaát ñoà thò. void set_distances(Vertex source, Weight distance[]) const; protected: int count; Weight adjacency[graph_size][graph_size]; }; Thuoäc tính count chöùa soá ñænh cuûa moät ñoái töôïng ñoà thò. Trong caùc öùng duïng, chuùng ta caàn boå sung caùc phöông thöùc ñeå nhaäp hay xuaát caùc thoâng tin cuûa moät ñoái töôïng ñoà thò, nhöng do chuùng khoâng caàn thieát trong vieäc hieän thöïc phöông thöùc distance ñeå tìm caùc ñöôøng ñi ngaén nhaát, chuùng ta xem chuùng nhö laø baøi taäp. Chuùng ta seõ giaû söû raèng lôùp Weight ñaõ coù caùc taùc vuï so saùnh. Ngoaøi ra, ngöôøi söû duïng seõ phaûi khai baùo trò lôùn nhaát coù theå coù cuûa Weight, goïi laø infinity. Chaúng haïn, chöông trình cuûa ngöôøi söû duïng vôùi taûi troïng laø soá nguyeân coù theå söû duïng thö vieän chuaån ANSI C++ vôùi ñònh nghóa toaøn cuïc nhö sau: const Weight infinity = numeric_limits::max(); Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 356
- Chöông 13 – Ñoà thò Chuùng ta seõ ñaët trò cuûa infinity vaøo caùc phaàn töû cuûa maûng distance töông öùng vôùi caùc caïnh töø khoâng toàn taïi nguoàn ñeán moãi ñænh. Phöông thöùc set_distance seõ tìm caùc ñöôøng ñi ngaén nhaát vaø caùc khoaûng caùch ngaén nhaát naøy seõ ñöôïc traû veà qua tham bieán distance[]. template void Digraph::set_distances(Vertex source, Weight distance[]) const /* post: Maûng distance chöùa ñöôøng ñi coù taûi troïng ngaén nhaát töø ñænh nguoàn ñeán moãi ñænh trong ñoà thò. */ { Vertex v, w; bool found[graph_size]; // Bieåu dieãn caùc ñænh trong S. for (v = 0; v < count; v++) { found[v] = false; distance[v] = adjacency[source][v]; } found[source]=true;// Khôûi taïo baèng caùch boû ñænh nguoàn vaøo S. distance[source] = 0; for(int i = 0; i < count; i++){ // Moãi laàn laëp boû theâm moät ñænh vaøo S. Weight min = infinity; for (w = 0; w < count; w++) if (!found[w]) if (distance[w] < min) { v = w; min = distance[w]; } found[v] = true; for (w = 0; w < count; w++) if (!found[w]) if (min + adjacency[v][w] < distance[w]) distance[w] = min + adjacency[v][w]; } } Ñeå öôùc ñoaùn thôøi gian caàn ñeå chaïy haøm naøy, chuùng ta thaáy raèng voøng laëp chính thöïc hieän n-1 laàn, trong ñoù n laø soá ñænh, vaø beân trong voøng laëp chính coù hai voøng laëp khaùc, moãi voøng laëp naøy thöïc hieän n-1 laàn. Vaäy caùc voøng laëp thöïc hieän (n-1)2 laàn. Caùc leänh beân ngoaøi voøng laëp chæ heát O(n), neân thôøi gian chaïy cuûa haøm laø O(n2). 13.6. Caây phuû toái tieåu 13.6.1. Ñaët vaán ñeà Giaûi thuaät tìm ñöôøng ñi ngaén nhaát cuûa phaàn treân coù theå ñöôïc aùp duïng vôùi maïng hay ñoà thò coù höôùng cuõng nhö maïng hay ñoà thò khoâng coù höôùng. Ví duï, hình 13.11 minh hoïa öùng duïng tìm caùc ñöôøng ñi ngaén nhaát töø ñænh nguoàn 0 ñeán caùc ñænh khaùc trong maïng. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 357
- Chöông 13 – Ñoà thò Hình 13.11 – Tìm ñöôøng ñi ngaén nhaát trong moät maïng Neáu maïng döïa treân cô sôû laø moät ñoà thò lieân thoâng G, thì caùc ñöôøng ñi ngaén nhaát töø moät ñænh nguoàn naøo ñoù seõ noái nguoàn naøy vôùi taát caû caùc ñænh khaùc trong G. Töø ñoù, nhö trong hình 13.11, neáu chuùng ta keát hôïp caùc ñöôøng ñi ngaén nhaát tính ñöôïc laïi vôùi nhau, chuùng ta coù moät caây noái taát caû caùc ñænh cuûa G. Noùi caùch khaùc, ñoù laø caây ñöôïc taïo bôûi taát caû caùc ñænh vaø moät soá caïnh cuûa ñoà thò G. Chuùng ta goïi nhöõng caây nhö vaäy laø caây phuû (spanning tree) cuûa G. Cuõng nhö phaàn tröôùc, chuùng ta coù theå xem moät maïng treân moät ñoà thò G nhö laø moät baûn ñoà caùc tuyeán bay, vôùi moãi ñænh bieåu dieãn moät thaønh phoá vaø taûi troïng treân moät caïnh laø giaù veù bay töø thaønh phoá naøy sang thaønh phoá kia. Moät caây phuû cuûa G bieåu dieãn moät taäp caùc ñöôøng bay cho pheùp caùc haønh khaùch hoaøn taát moät chuyeán du lòch qua khaép caùc thaønh phoá. Dó nhieân raèng, haønh khaùch caàn phaûi thöïc hieän moät soá tuyeán bay naøo ñoù moät vaøi laàn môùi hoaøn taát ñöôïc chuyeán du lòch. Ñieàu baát tieän naøy ñöôïc buø ñaép bôûi chi phí thaáp. Neáu chuùng ta hình dung maïng trong hình 13.11 nhö moät heä thoáng ñieàu khieån taäp trung, thì ñænh nguoàn töông öùng vôùi saân bay trung taâm, vaø caùc ñöôøng ñi töø ñænh naøy laø nhöõng haønh trình bay. Moät ñieàu quan troïng ñoái vôùi moät saân bay theo heä thoáng ñieàu khieån taäp trung laø giaûm toái ña chi phí baèng caùch choïn löïa moät heä thoáng caùc ñöôøng bay maø toång chi phí nhoû nhaát. Ñònh nghóa: Moät caây phuû toái tieåu (minimal spanning tree) cuûa moät maïng lieân thoâng laø caây phuû maø toång caùc taûi troïng treân caùc caïnh cuûa noù laø nhoû nhaát. Maëc duø vieäc so saùnh hai caây phuû trong hình 13.12 laø khoâng khoù khaên, nhöng cuõng khoù maø bieát ñöôïc coøn coù caây phuû naøo coù trò nhoû hôn nöõa hay khoâng. Baøi toaùn cuûa chuùng ta laø xaây döïng moät phöông phaùp xaùc ñònh moät caây phuû toái tieåu cuûa moät maïng lieân thoâng. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 358
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Đề thi cấu trúc dữ liệu và giải thuật có đáp án (2007-2008)
17 p |
3080 |
884
-
Chương 1: Nhập môn cấu trúc dữ liệu
33 p |
432 |
171
-
Các cấu trúc dữ liệu
7 p |
223 |
125
-
Cấu trúc dữ liệu 2005 P18
16 p |
92 |
23
-
Cấu trúc dữ liệu 2005 P15
10 p |
77 |
20
-
Cấu trúc dữ liệu 2005 P17
6 p |
74 |
17
-
Cấu trúc dữ liệu 2005 P16
8 p |
88 |
17
-
Cấu trúc dữ liệu 2005 P14
12 p |
72 |
17
-
Cấu trúc dữ liệu 2005 P12
34 p |
76 |
15
-
Cấu trúc dữ liệu 2005 P10
46 p |
68 |
13
-
Cấu trúc dữ liệu 2005 P11
22 p |
51 |
12
-
Cấu trúc dữ liệu 2005 P9
54 p |
90 |
12
-
Cấu trúc dữ liệu 2005 P5
16 p |
43 |
9
-
Cấu trúc dữ liệu 2005 P4
24 p |
40 |
9
-
Cấu trúc dữ liệu 2005 P6
46 p |
39 |
7
-
Cấu trúc dữ liệu 2005 P3
14 p |
29 |
7
-
Cấu trúc dữ liệu 2005 P7
12 p |
31 |
6

Set-Cookie: TLDEVNamespace=u2n6ruhqgc3lgssssc9qngc3e3; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Chỉ thị số 15/2001/CT-TTg
Chia sẻ: Pham Luat | Ngày: | Loại File: PDF | Số trang:3
64
lượt xem 3
download
lượt xem 3
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20091025/lawktkt5/80x100/1214.jpg)
##
Chỉ thị số 15/2001/CT-TTg
Mô tả tài liệu
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Chỉ thị số 15/2001/CT-TTg về việc tăng cường quản lý và chống thất thu ngân sách nhà nước năm 2001 do Thủ Tướng Chính Phủ ban hành
Chủ đề:
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

WARC-Type: response

Content-Type: application/http; msgtype=response

WARC-Identified-Payload-Type: application/xhtml+xml

Server: Apache/2.2.31 (CentOS)

Connection: close

Pragma: no-cache

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Set-Cookie: TLDEVNamespace=djnq9gn480jpmihnn37jk2o775; path=/; domain=.tailieu.vn; HttpOnly

Vary: Accept-Encoding

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


markdown:
# Chương 16: Điện từ trường
Chia sẻ: Pham Tuan Anh | Ngày: | Loại File: PDF | Số trang:7
lượt xem 133
download
![](http://image.tlvnimg.com/document/thumbnail/2010/20100919/kklick/80x100/chuong_16_dien_tu_truong_1552.jpg)
##
Chương 16: Điện từ trường
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Điện tường và từ trường không tồn tại độc lập mà có mối liên hệ chặt chẽ với nhau. Từ trường biến thiên sẽ làm xuất hiện điện trường xoáy và ngược lại, điện trường biên thiên sẽ làm xuất hiện từ trường. Như vậy, điện trường và từ trường có thể chuyển hoá qua lại, chúng là hai mặt của một trường thống nhất – trường điện từ.
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Chương 16: Điện từ trường
- 336 Giáo Trình Vật Lý Đại Cương – Tập 1: Cơ – Nhiệt – Điện Chương 16 ĐIỆN TỪ TRƯỜNG Điện tường và từ trường không tồn tại độc lập mà có mối liên hệ chặt chẽ với nhau. Từ trường biến thiên sẽ làm xuất hiện điện trường xoáy và ngược lại, điện trường biên thiên sẽ làm xuất hiện từ trường. Như vậy, điện trường và từ trường có thể chuyển hoá qua lại, chúng là hai mặt của một trường thống nhất – trường điện từ. Nhà Bác học vĩ đại người Anh, Maxwell đã khám phá ra mối liên hệ này và xây dựng nên lý thuyết tổng quát về điện – từ trường. § 16.1 THUYẾT MAXWELL VỀ ĐIỆN TỪ TRƯỜNG 1 – Luận điểm Maxwell thứ nhất – điện trường xoáy: Xét một mạch kín đứng yên trong từ trường biến thiên. Từ thông qua mạch kín đó thay đổi làm trong mạch xuất hiện dòng điện cảm ứng. Sự xuất hiện dòng điện cảm ứng, chứng tỏ trong mạch phải tồn tại một trường lực lạ. Phân tích các kết quả thực nghiệm của Faraday, Maxwell cho rằng, trường lực lạ ở đây chính là điện trường. Nhưng điện trường này không phải là điện trường tĩnh, vì như ta đã biết, điện trường tĩnh không thể làm di chuyển điện tích theo mạch kín được. Maxwell cho rằng điện trường đó phải là điện trường xoáy. Theo Maxwell, mạch điện kín không phải là nguyên nhân gây ra điện trường xoáy, mà nó chỉ là phương tiện giúp ta nhận biết sự tồn tại của điện trường xoáy. Nguyên nhân gây ra điện trường xoáy chính là sự biến thiên của từ trường. Từ đó Ông đưa ra luận điểm thứ nhất: “Mọi từ trường biên thiên theo thời gian đều làm xuất hiện một điện trường xoáy”. Khác với điện trường tĩnh, điện → trường xoáy có các đường sức khép kín và B lưu thông của vectơ cường độ điện trường xoáy dọc theo một được cong bất kỳ không những phụ thuộc vào vị trí điểm đầu và điểm cuối, mà còn phụ thuộc vào hình dạng đường cong mà ta tính lưu thông. Vì thế lưu thông của vectơ cường độ điện trường xoáy dọc theo một được cong kín bất kỳ là khác không. Chính vì vậy, điện trường xoáy đóng → vai trò là trường lực lạ, tạo ra suất điện động E làm di chuyển điện tích trong mạch, tạo thành dòng điện khép kín. Hình 16.1: Từ trường biến thiên sinh ra điện trường xoáy Dựa vào định luật Faraday về hiện tượng cảm ứng điện từ, Maxwell đã xây dựng một phương trình diễn tả định lượng luận điểm thứ nhất của mình:
- Chương 16: ĐIỆN TỪ TRƯỜNG 337 → → → ∂B → ∫Ed (L) = −∫ (S) ∂t dS (16.1) Phương trình (16.1) được gọi là phương trình Maxwell – Faraday ở dạng tích phân. Nó diễn tả đặc tính xoáy của điện trường. Trong đó, vế phải thể hiện tốc độ biến thiên của từ thông qua diện tích S; vế trái là lưu thông của vectơ cường độ điện trường xoáy dọc theo chu tuyến L bao quanh S. Ở dạng vi phân, phương trình Maxwell – Faraday có dạng: → → ∂B rot E = − (16.2) ∂t → trong đó, toán tử vi phân rot E là một vec tơ có các thành phần được xác định bởi → → → i j k → ∂ ∂ ∂ định thức: rot E = (16.3) X ∂x ∂y ∂z Ex Ey Ez + → Do đó (16.2) tương đương với hệ ba phương trình đại số: ~ ∂D H ∂t ∂E z ∂E y ∂B - − =− x ∂y ∂z ∂t Hình 16.2: Dòng điện ∂E x ∂E z ∂B y dịch sinh ra từ trường − =− (16.4) ∂z ∂x ∂t ∂E y ∂E x ∂B − =− z ∂x ∂y ∂t 2 – Luận điểm Maxwell thứ hai – dòng điện dịch: Ở luận điểm thứ nhất, Maxwell cho rằng mọi từ trường biến thiên đều sinh ra điện trường (xoáy). Phân tích các hiện tượng điện từ khác Maxwell khẳng định phải có điều ngược lại: “Mọi điện trường biến thiên theo thời gian đều làm xuất hiện từ trường” – luận điểm thứ hai của Maxwell. Vì từ trường là dấu hiệu cơ bản nhất và tất yếu của mọi dòng điện, nên, nếu sự biến thiên của điện trường tạo ra từ trường thì sự biến thiên của điện trường đó có tác dụng như một dòng điện. Maxwell gọi đó là dòng điện dịch, để phân biệt với dòng điện dẫn – là dòng chuyển dời có hướng của các điện tích. Dòng điện dịch có tính chất cơ bản giống dòng điện dẫn ở chỗ nó gây ra từ trường. Nhưng nó không giống dòng điện dẫn về bản chất: dòng điện dẫn là do sự chuyển dời có hướng của các điện tích trong một môi trường dẫn nào đó; còn dòng điện dịch là do sự biến thiên của điện trường sinh ra. Vì thế, khác với dòng điện
- 338 Giáo Trình Vật Lý Đại Cương – Tập 1: Cơ – Nhiệt – Điện dẫn, dòng điện dịch có thể tồn tại ngay cả trong điện môi hoặc trong chân không; dòng điện dịch không có tác dụng nhiệt Joule – Lenz như dòng điện dẫn. Để hình dung về dòng điện dịch, ta xét một mạch điện xoay chiều gồm tụ điện C mắc nối tiếp với một bóng đèn. Đèn sáng bình thường, điều này có phải dòng điện đã chạy qua tụ điện không? Không phải! Do tụ điện liên tục phóng điện và nạp điện nên trong dây dẫn và đèn luôn tồn tại dòng điện dẫn xoay chiều. Còn giữa hai bản tụ điện, mạch hở nên không có dòng điện dẫn. Nhưng hiệu điện thế giữa hai bản tụ luôn biến thiên làm điện trường trong lòng tụ biến thiên, sinh ra dòng điện dịch. Như vậy dòng điện dẫn trong dây dẫn của mạch điện đã được đóng kín bằng dòng điện dịch trong lòng tụ điện. Với giả thuyết về dòng điện dịch, bằng cách vận dụng định lý Ampère về lưu thông của vectơ cường độ từ trường, Maxwell đã thiết lập được biểu thức định lượng cho luận điểm thứ hai của mình: → → → → ∂D → ∫Hd (L) = ∫( j + (S) ∂t )d S (16.5) Phương trình (16.5) được gọi là phương trình Maxwell – Ampère ở dạng tích phân. → → ∂D Trong đó j là mật độ dòng điện dẫn, là mật độ dòng điện dịch; vế phải biểu ∂t diễn cường độ dòng điện toàn phần (gồm dòng điện dẫn và dòng điện dịch) chảy qua tiết diện S; vế trái là lưu thông của vectơ cường độ từ trường dọc theo chu tuyến L bao quanh S. Ở dạng vi phân, phương trình Maxwell – Ampère có dạng: → → → ∂D rot H = j + (16.6) ∂t Phương trình (16.6) tương đương với hệ ba phương trình đại số: ∂H z ∂H y ∂D x − = jx + ∂y ∂z ∂t ∂H x ∂H z ∂D y − = jy + (16.7) ∂z ∂x ∂t ∂H y ∂H x ∂D z − = jz + ∂x ∂y ∂t 3 – Hệ phương trình Maxwell Theo các luận điểm của Maxwel, từ trường biến thiên sinh ra điện trường → ∂H xoáy và ngược lại, mà sự biến thiên của từ trường là bất kỳ, nên đạo hàm ∂t cũng biến thiên theo thời gian, do đó điện trường xoáy xuất hiện cũng biến thiên theo thời gian và nó lại gây ra một từ trường biến thiên, … Như vậy, điện trường
- Chương 16: ĐIỆN TỪ TRƯỜNG 339 và từ trường liên hệ chặt chẽ với nhau và chuyển hoá lẫn nhau. Chúng tồn tại đồng thời trong không gian tạo thành trường thống nhất – trường điện từ. Khái niệm về trường điện từ được Maxwell nêu lên đầu tiên và để diễn tả định lượng, ông đã thiết lập các phương trình – gọi là hệ phương trình Maxwell: - Dạng vi phân: → ∂B → rot E = − (16.8a) ∂t → → ∂D → rot H = j + (16.9a) ∂t → div D = ρ (16.10a) → div B = 0 (16.11a) - Dạng tích phân: → → → ∂B ∫Ed (L) =−∫ (S ) ∂t (16.8b) → → → →∂D → ∫Hd (L) = ∫( j + (S) ∂t )d S (16.9b) → → ∫ Dd S = ∑q ( S) (16.10b) → → ∫ Bd S = 0 (S) (16.11b) Phương trình (16.8a) và (16.8b) là phương trình Maxwell – Faraday ở dạng vi phân và tích phân, diễn tả luận điểm thứ nhất của Maxwell về mối liên hệ giữa từ trường biến thiên và điện trường xoáy. Phương trình (16.9a) và (16.9b) là phương trình Maxwell – Ampère ở dạng vi phân và tích phân, diễn tả luận điểm thứ hai của Maxwell về mối liên hệ giữa điện trường biến thiên và từ trường. Các phương trình (16.10a), (16.10b) và (16.11a), (16.11b) diễn tả định lý Ostrogradsky – Gauss ở dạng vi phân, tích phân đối với điện trường và từ trường. Ngoài các phương trình cơ bản trên, còn có các phương trình diễn tả mối → → → → quan hệ giữa các đại lượng đặc trưng cho trường ( E, D, B, H ) với các đại lượng đặc trưng cho tính chất của môi trường (µ, ε, σ ): → → + Môi trường điện môi: D = εε o E (16.12) → → + Môi trường điện dẫn: j = σ E (16.13)
- 340 Giáo Trình Vật Lý Đại Cương – Tập 1: Cơ – Nhiệt – Điện → → + Môi trường từ hoá: B = µµ o H (16.14) Trong các phương trình Maxwell, các đại lượng đặc trưng cho trường đều là các đại lượng biến thiên theo toạ độ và thời gian. Nói cách khác, chúng là hàm của x, y, z, t. Hệ phương trình Maxwell bao hàm tất cả các định luật cơ bản về điện và từ. Trường tĩnh điện, trường tĩnh từ và sóng điện từ chỉ là những trường hợp riêng của điện từ trường mà thôi. 4 – Ý nghĩa của thuyết Maxwell Lý thuyết trường điện từ của Maxwell thống nhất giữa điện trường và từ trường (công bố vào những năm đầu thập niên 60 của thế kỉ XIX), là một bước phát triển hoàn thiện những hiểu biết của con người về điện, từ. Trước đó, những hiểu biết của con người về điện, từ còn rời rạc; người ta quan niệm rằng điện và từ là hai lĩnh vực không liên quan nhau. Maxwell đã phát triển các ý tưởng của Faraday về điện, từ một cách sâu sắc và đã xây dựng lý thuyết thống nhất giữa điện và từ - lý thuyết trường điện từ - một cách hoàn hảo. Thuyết Maxwell không những giải thích triệt để các hiện tượng điện từ đã biết mà nó còn cho phép tiên đoán sự tồn tại của sóng điện từ (mà gần 30 năm sau thực nghiệm mới xác lập được). Nghiên cứu bằng lý thuyết về các tính chất của sóng điện từ, Maxwell đã khẳng định ánh sáng cũng là sóng điện từ. Với những đóng góp to lớn của mình, Maxwell được đánh giá là một trong những nhà vật lý đi tiên phong, mở ra bước ngoặt trong lịch sử nhận thức của nhân loại. § 16.2 SÓNG ĐIỆN TỪ TỰ DO 1 – Hệ phương trình Maxwell mô tả sóng điện từ tự do: Điện từ trường lan truyền trong không gian theo thời gian tạo thành sóng điện từ. Nếu ta xét sự lan truyền của sóng điện từ trong môi trường không dẫn và → không có các điện tích thì j = 0 và ρ = 0, khi đó ta có sóng điện từ tự do và hệ phương trình Maxwell mô tả sóng điện từ tự do là: → → → ∂B → ∂D rot E = − ; rot H = (16.15) ∂t ∂t → → div D = 0 ; div B = 0 (16.16) → → → → D = εε o E ; B = µµ o H (16.17)
- Chương 16: ĐIỆN TỪ TRƯỜNG 341 2 – Tính chất tổng quát của sóng điện từ: → Giải hệ phương trình (16.15), (16.16) và (16.17) ta xác định được vectơ E → và H đặc trưng cho điện từ trường tại một điểm trong không gian. Chúng là những hàm tuần hoàn của thời gian t. Từ đó, rút ra được những tính chất tổng quát của sóng điện từ. Những tính chất này đã được thực nghiệm kiểm chứng. Tính chất 1: Sóng điện từ là sóng ngang: tại mỗi điểm trong không gian có sóng → → điện từ, các vectơ E và H luôn dao động theo hai phương vuông góc nhau và vuông góc với phương truyền sóng. Tính chất 2: Khác với sóng cơ học, sóng điện từ truyền được cả trong môi trường vật chất và trong chân không. Tính chất 3: Vận tốc lan truyền sóng điện từ trong chân không là c = εoµ o = c 3.10 8 m/s; và trong môi trường vật chất đồng nhất và đẳng hướng là v = , với n n= εµ là chiết suất tuyết đối của môi trường; ε và µ là hệ số điện môi và từ môi của môi trường đó. Vì ε , µ > 1 nên n > 1 và v < c. Tính chất 4: Sóng điện từ có mang năng lượng. Năng lượng sóng điện từ chính là năng lượng của điện từ trường. Mật độ năng lượng sóng điện từ là: 1 1 w= εε o E 2 + µµ o H 2 (16.18) 2 2 3 – Thang sóng điện từ: 10 - 12 10 - 10 10 - 8 10 - 6 10 - 4 10 - 2 1 10 2 10 4 λ (cm) Tia tử ngoại A /s khả kiến Tia hồng Sóng vô tuyến ngoại Tia γ Tia X VHF UHF MW SHF SW LW f 3.10 14 3.10 10 3.10 8 3.10 4 3 (MHz) Hình 16.3: Thang sóng điện từ. Sóng điện từ đơn sắc là sóng điện từ phát ra từ một nguồn có tần số xác định. Khi truyền trong môi trường nhất định, sóng điện từ đơn sắc có một bước c.T λ o sóng xác định: λ = v.T = = (16.19) n n trong đó λo = c.T là bước sóng của sóng điện từ trong chân không.
- 342 Giáo Trình Vật Lý Đại Cương – Tập 1: Cơ – Nhiệt – Điện Người ta phân loại sóng điện từ đơn sắc theo tần số hay bước sóng (trong chân không). Bảng phân loại sóng điện từ được gọi là thang sóng điện từ. 4 - Ứng dụng sóng điện từ trong thông tin liên lạc: Vì sóng điện từ có thể lan truyền được cả trong môi trường vật không khí lẫn chân không với vận tốc rất lớn (v ≈ 300 000 km/s), nên sóng điện từ được ứng dụng trong thông tin liên lạc vô tuyến. Thông tin (âm thanh, hình hảnh, …) được mã hoá thành các tín hiệu điện và được trộn lẫn với sóng điện từ cao tần (còn gọi là biến điệu, hay điều chế sóng điện từ – modulation), rồi phát đi trong không gian. Máy thu sẽ thu được sóng điện từ cao tần này, sau đó tách sóng, tái tạo lại thông tin ban đầu. Miền sóng điện từ có tần số nhỏ hơn 30GHz được dùng trong thông tin liên lạc vô tuyến nên gọi là miền sóng vô tuyến. Trong miền này, người ta chia làm nhiều băng tần: • Băng sóng dài LW – Long Wave (từ 30kHz đến 300kHz): dùng truyền thanh trong các thành phố nhỏ (đài địa phương). • Băng sóng trung MW – Medium Wave (từ 300kHz đến 3MHz): dùng truyền thanh trong khu vực lớn. • Băng sóng ngắn SW – Short Wave (từ 3MHz đến 30MHz): bị phản xạ mạnh ở tầng điện li, nên sóng điện từ ở dải tần này có thể truyền đi vòng quanh thế giới. Tuy nhiên, nó bị ảnh hưởng nhiều bởi thời tiết. • Băng sóng siêu tần số VHF – Very High Frequency (từ 30MHz đến 300MHz): dùng trong vô tuyến truyền hình, FM. Sóng điện từ ở dải tần này có tính chất truyền thẳng nên không truyền đi xa được (do bề cong của trái đất). • Băng sóng cực tần số UHF – Ultra High Frequency (từ 300MHz đến 3000MHz): dùng trong vô tuyến truyền hình. Sóng điện từ ở dải tần này có tính chất truyền thẳng và ít bị nhiễu. • Băng sóng siêu cao tần SHF – Super High Frequency (lớn hơn 3GHz): dùng liên lạc giữa các con tàu vũ trụ với mặt đất. Ngoài ứng dụng thông tin liên lạc bằng vô tuyến, ngày nay, với sự phát triển mạnh của laser và sợi quang học, miền sóng khả kiến còn được ứng dụng thông tin liên lạc hữu tuyến rất hiệu quả.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
15 đề và đáp án Lý thuyết trường điện từ
83 p |
1191 |
441
-
Chương 13: TỪ TRƯỜNG TĨNH
23 p |
463 |
131
-
Từ trường
6 p |
366 |
124
-
Điện trường
3 p |
370 |
96
-
Chương 4: Từ trường-từ trường của các loại dòng điện
11 p |
357 |
83
-
Đề tài " CHUYỂN ĐỘNG CỦA ĐIỆN TÍCH TRONG ĐIỆN TỪ TRƯỜNG "
10 p |
207 |
50
-
Lịch sử Điện từ trường và Thuyết tương đối
7 p |
129 |
36
-
Hướng dẫn giải bài tập Điện từ trường - Định hướng tuần 1 - 2 - 3 - GV. Trần Thiên Đức
21 p |
76 |
31
-
Những tác hại của điện từ trường
6 p |
86 |
22
-
Bài tập ôn tập từ trường dòng điện môn Vật lý lớp 11 - Cơ bản
8 p |
189 |
21
-
Giáo án Vật lý 12 - ĐIỆN TỪ TRƯỜNG
5 p |
177 |
18
-
Điện từ trường và sức khoẻ con người
6 p |
39 |
6
-
TRẮC NGHIỆM VẬT LÝ - CHƯƠNG BỐN : ĐIỆN TỪ TRƯỜNG
5 p |
31 |
4
-
Tiết 33: ĐIỆN TỪ TRƯỜNG
4 p |
39 |
4
-
Vật lý 12 Phân ban: BÀI 32 : ĐIỆN TỪ TRƯỜNG
0 p |
49 |
2
-
ÔN TẬP THI TN NĂM 2011 PHẦN ĐIỆN TỪ TRƯỜNG
5 p |
56 |
2
-
Vật lý 12: Dao động điện từ
9 p |
18 |
1

Set-Cookie: TLDEVNamespace=91d60mj96uij0055q0rmqkabt1; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Lựa chọn chế độ đo sáng (Metering) - Phần 2
Chia sẻ: Nguyen Hoang Phuong Uyen | Ngày: | Loại File: PDF | Số trang:9
lượt xem 85
download
![](http://image1.tailieu.vn/document/thumbnail/2010/20100811/civic123/80x100/lua_chon_che_do_do_sang_2_0955.jpg)
##
Lựa chọn chế độ đo sáng (Metering) - Phần 2
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Chụp các chủ đề tối Bởi vì bộ đo sáng trong máy ảnh được thiết lập để lưu lại mọi thứ dựa trên mức sáng trung bình (18% trên thang độ xám), các chủ đề tối đôi khi sẽ trở nên sáng quá khi bạn thử tăng mức sáng trung bình này lên. Để khắc phục điều này, bạn có thể sử dụng exposure compensation, sử dụng chế độ đo sáng spot metering (nếu máy bạn hỗ trợ) hay đo sáng vào vùng có độ sáng lớn hơn. Phần lớn các máy ảnh đều có khả năng lưu (khóa) lại...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Lựa chọn chế độ đo sáng (Metering) - Phần 2
- Lựa chọn chế độ đo sáng (Metering) - Phần 2 Bài này dành cho các dòng máy ảnh có các chế độ chụp Av,Tv,M Chụp các chủ đề tối Bởi vì bộ đo sáng trong máy ảnh được thiết lập để lưu lại mọi thứ dựa trên mức sáng trung bình (18% trên thang độ xám), các chủ đề tối đôi khi sẽ trở nên sáng quá khi bạn thử tăng mức sáng trung bình này lên. Để khắc phục điều này,
- bạn có thể sử dụng exposure compensation, sử dụng chế độ đo sáng spot metering (nếu máy bạn hỗ trợ) hay đo sáng vào vùng có độ sáng lớn hơn. Phần lớn các máy ảnh đều có khả năng lưu (khóa) lại thông tin về độ phơi sáng và cho bạn phối cảnh lại lại trước khi chụp. Điều này thông thường được thực hiện ở chế độ chụp 1 ảnh một (Single Shot Focus) bằng cách focus vào chủ đề, giữ nguyên nút chụp ở vị trí 1/2 trong khi bạn phối cảnh lại. Lựa chọn khác nếu máy ảnh của bạn có nút khóa exposure, bạn có thể sử dụng nó. Giá trị ghi nhận được sẽ được giữ cho đến khi ảnh được chụp. Vì thế bạn cso thể thay đổi tiêu cự, focus hay phối cảnh lại tấm hình. Khi nút chụp được nhấn và ảnh đã được lưu lại, việc khóa giá trị phơi sáng sẽ bị chấm dứt và bạn sẵn sàng để chụp tấm hình kế tiếp. Đối với những ảnh có một lượng lớn các vùng tối, điều chỉnh độ phơi sáng có thể lên đến giá trị tương đương 2 khẩu độ (f-stop). Như bạn thấy, các vùng màu đen có thang độ xám lớn hơn do bộ đo sáng óố gắng đưa những vùng này về gần điểm đo sáng trung bình. Để những vùng màu đen giữ màu nhưng chúng vốn có, tôi sử dụng độ bù sáng là -1 2/3 stop Chụp các chủ đề sáng
- Trừ khi bạn là một fan của tuyết có màu xám hay những hình ảnh bị mất màu trắng, thông thường việc chụp các chủ đề sáng cũng yêu cầu phải điều chỉnh độ phơi sáng. Giống như chụp các chủ đề tối, khi bộ đo sáng đánh giá ánh sáng của khung cảnh (một vùng tuyết trắng chẳng hạn), nó sẽ cố gắng thể hiện khung cảnh toàn tuyết trắng ở mức sáng trung bình. Đó là nguyên nhân bức ảnh của bạn trông có vẻ xám đi (hoặc nhìn trông hơi xanh xanh) Các khung cảnh sáng cũng có những vẫn đề như các khung cảnh tối. Bộ đo sáng cố gắng để chủ đề chính nằm ở mức sáng trung bình, làm cho những vùng trắng trông bị xám đi. Bằng cách sử dụng exposure compensation và chụp tấm hình ở mức bù sáng là +2 stop, lớp tuyết trông sáng trở lại trong khi vẫn giữ được nguyên chi tiết. Bằng cách +2 stop vào độ phơi sáng, các vùng trắng sẽ trở lại như chúng vốn có. Chụp ảnh với nguồn sáng ở phía sau Những khung cảnh có nguồn sáng phía sau là những tình huống khó khăn nhất để bộ đo sáng thực hiện chính xác công việc. Thông thường bạn sẽ có một
- nguồn rất sáng, như mặc trời, đến mức làm tràn ngập bộ đo sáng. Để khắc phục, bộ đo sáng cố gắng đưa những vùng sáng nhất về trong giới hạn thông thường. Điều này sẽ làm cho bạn chỉ nhìn thấy cái bóng đen của người hay của các chủ đề khác. Thủ thuật Giải pháp tốt nhất với nguồn sáng ở phía sau là sử dụng đèn flash để giúp chiếu sáng chủ đề. Trong tình huống này, sử dụng center-weighted hay spot metering là lựa chọn tốt nhất vì bạn sẽ luôn luôn đo sáng chủ đề và loại bỏ phần nền sáng. Trong tình huống hậu cảnh quá sáng, bộ đo sáng sẽ bị tràn ngập bởi ánh sáng của hậu cảnh và làm cho chủ đề chính bị under-exposure. Bằng cách chuyển sang chế độ spot metering, tôi có thể thay đổi đâu là nguồn sáng chính và kết quả là tấm ảnh. Độ phơi sáng bị thay đổi đi 3 stop. Mặc dù tôi bị mất chi tiết ở những vùng sáng nhưng tôi lại có thể nhìn rõ chủ đề trong tấm ảnh là gì. Bằng cách chuyển sang spot metering, tôi có được độ phơi sáng tốt hơn, cho phép tôi ghi lại chi tiết về chủ đề mặc dù bị mất đi chi tiết ở hậu cảnh.
- Khi bạn không thể chuyển sang chế độ đo sáng khác vì một vài lý do nào đó thì đó là thời điểm cho bạn sáng tạo bằng cách sử dụng một kĩ thuật khác. Bạn hãy đo sáng bầu trời mà không có mặt trời trong khung hình (tôi giả sử bạn đang chụp với nguồn sáng phía sau là mặt trời) hoặc đo sáng vào mặt đất. Ngoài ra bạn cũng có thể di chuyển đến gần chủ đề để chủ đề chiếm trọn khung hình, sau đó nhấn 1/2 nút chụp để bộ đo sáng hoạt động. Nếu máy ảnh của bạn có nút khóa exposure, khóa giá trị bạn đo được rồi di chuyển để phối lại lại tấm hình bạn muốn chụp (tất nhiên, nếu không có nút khóa này, bạn sẽ phải giữ nguyên nút chụp ở vị trí 1/2 trong khi di chuyển và phối cảnh). Các kĩ thuật sáng tạo Chiếc máy ảnh dSLR của bạn nói chung sẽ có rất nhiều chế độ chụp được thiết kế để bạn có thể dễ dàng chụp những đối tượng khác nhau với các thiết lập tối ưu. Tuy nhiên các thiết lập này không phải luôn luôn đưa ra được những tấm ảnh hấp dẫn. Trong phần này tôi sẽ liệt kê một số chế độ khác nhau và giải thích tại sao bạn phải thay đổi những thiết lập này. Trong quá trình đó, bạn sẽ học hỏi nhiều hơn về lựa chọn độ phơi sáng, qua đó cho phép bạn đỡ bị lệ thuộc vào các chế độ này và tiến tới trình độ cao hơn trong lĩnh vực nhiếp ảnh. Ảnh chân dung Đã là hiển nhiên, chế độ chụp ảnh chân dung (Portrait mode) đưa ra cho bạn DOF (Depth Of Field - độ nét sâu (PA)) nhỏ nhất nhằm làm mờ hậu cảnh như
- trong. Phụ thuộc vào kiểu chân dung bạn muốn chụp mà hậu cảnh bị làm mờ có thể chỉ ở mặt mà bạn muốn. Việc chụp ảnh chân dung ở ngoài ngày càng trở nên phổ biến khi mà chủ đề được thể hiện như là một thành phần của khung hình. Trong ví dụ này, bạn cần DOF lớn hơn để hiển thị khung cảnh xung quanh quanh chủ đề. Với kiểu ảnh chân dung này, bạn cần chuyển qua chế độ Aperture Priority (Av). Bạn có thể thấy kết quả của việc chụp trong chế độ Av với một ống kính tele ở khẩu độ f/8 Khi bạn muốn thêm vào một số vùng xung quanh ảnh, chuyển từ chế độ Portrait sang Av. Chủ đề và các vùng xung quanh sẽ được lấy nét còn hậu cảnh phía xa sẽ vẫn bị mờ. Kết quả là bạn sẽ có một tấm hình tốt hơn đối với cả chủ đề và hậu cảnh. Ảnh phong cảnh Chế độ này ngược lại với chế độ Portrait, nó sử dụng DOF lớn nhất có thể trong khi vẫn giữ tốc độ chập ở mức cao đủ để bạn có thể cầm máy trên tay. Trong các tình huống thiếu sáng (thường là thời điểm tốt nhất để chụp ảnh phong cảnh) như lúc mặt trời mọc hay mặt trời lặn thì điều này đồng nghĩa với việc bạn sẽ có DOF nhỏ hơn giá trị bạn muốn khi chụp ảnh phong cảnh. Những lúc như thế này, chế độ Av là giải pháp. Lưu ý
- Bạn sẽ có kết quả tốt hơn nếu sử dụng tripod khi có thể. Có một nguyên tắc thông dụng trong nhiếp ảnh là bạn không nên sử dụng tay cầm máy ảnh bất cứ khi nào độ phơi sáng dài hơn chiều dài tiêu cự của ống kính. Nói một cách khác, nếu bạn đang sử dụng ống kính 50mm, bạn không nên cầm máy trên tay để chpj nếu tốc độ chập nhỏ hơn 1/60 giây. Sẽ gần như là không thể nếu chụp trong chế độ Landscape. Vì vậy tôi sử dụng Av cùng với một tripod, tốc độ chập là 1/4 giây. Trong tình huống thiếu sáng, chế độ Landscape nói chung sẽ không làm việc. Trong tình huống này, tôi sử dụng Av cùng với một tripod để có thời gian phơi sáng lâu hơn. Chụp ảnh vào buổi tối Một trong những điểm mạnh của máy ảnh dSLR là bạn có thể sử dụng tốc độ chập lớn hơn là máy ảnh cá nhân. Mặc dù nhiều máy ảnh dSLR có cả chế độ chụp tối (Night mode) nhưng nó thường sử dụng thời gian phơi sáng không lâu (vẫn đủ lâu để bạn phải sử dụng tripod), hiếm khi nhiều hơn 1 giây. Bằng cách chuyển sang chế độ Manual, bạn có thể sử dụng thiết lập Bulb. Bulb có nghĩa là màn chập sẽ mở cho đến khi nút chụp được nhấn. Phần lớn máy ảnh có một đoạn dây cáp hoặc một bộ điều khiển từ xa để sử dụng cho mục đích này. Bạn có thể
- chụp một tấm ảnh với với gian bằng thời gian hoạt động của nguồn điện. Thời gian phơi sáng là 16 phút, sử dụng để chụp ảnh những vệt sao. Bằng cách ngắm máy ảnh lên phía bắc và để màn chập mở trong một thời gian dài, bạn có thể chụp được sự chuyển động của những ngôi sao trên bầu trời. Các vệt sao cần thời gian chụp lâu hơn là chế độ Night có thể làm. Trong tình huống này, bạn cần chuyển sang chế độ Manual và sử dụng cáp điều khiển để có thể chụp với thời gian phơi sáng là 1 giờ hoặc lâu hơn. Đối với những tấp ảnh chụp đêm từ trái đất như những tấm ảnh pháo hoa, một lần nữa chế độ bulb lại là một lựa chọn chính xác. Thời gian phơi sáng ở mức 6 giây và 8 giây ở khẩu độ f/22 để lưu lại những chùm pháo hoa cùng với vệt sáng của nó. Thời gian phơi sáng 6 giây cho phép lưu lại nhiều chùm pháo hoa Hãy đừng sợ khi chụp thử. Ở đây tôi sử dụng thời gian phơi sáng là 8 giây để có nhiều chùm pháo hoa với những vệt sáng dài hơn. Chụp ảnh ở chế độ Macro và Close-up Ở hai chế độ này, thông thường cái bạn muốn là DOF lớn nhất có thể. Do khoảng cách chụp là rất nhỏ, thậm chí với khẩu độ f/16 cũng không cho bạn thêm nhiều DOF. Nhưng cũng như các ví dụ trên, bạn không cần phải sử dụng những
- thiết lập mặc định này. Đôi lúc bạn cần một cái gì đó mang tính thẩm mĩ cao hơn. Hiển thị hình ảnh mà chế độ macro mang lại ở giá trị khẩu độ là f/16. Trong ví dụ tiếp theo, Sử dụng khẩu độ lớn hơn để giảm DOF. Bằng cáh thay đổi khẩu độ lên f/8, chỉ phần cuối của nhị hoa được lấy focus, do vậy hậu cảnh trông sẽ mềm mại hơn. Bằng việc chuyển sang chế độ Av, tôi giảm DOF để tấm ảnh nhìn có tính thẩm mĩ cao hơn Chụp ảnh thể thao Sau tất cả những ví dụ trên, bạn có lẽ phân vân tại sao máy ảnh của bạn lại có chế độ ưu tiên tốc độ chập (Shutter Priority hay Time Priority - Tv). Khi bạn chụp trong chế độ Tv (đôi khi còn gọi là Sports mode), bạn có thể tối ưu để có tốc độ chập nhanh hơn nhằm làm "đóng băng" các chuyển động Chế độ Tv tối ưu tốc độ chập nhằm làm "đóng băng" chuyển động. Nhưng những tấm ảnh tĩnh khi mà tất cả các chuyển động đều như ngưng lại không phải luôn luôn là lựa chọn tốt nhất. Bằng cách chuyển sang chế độ Tv và chọn tốc độ chụp chậm, bạn có thể thu lại sự chuyển động của khung cảnh, cho bạn cảm giác thực giống.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
12 cách chọn ISO [độ nhạy sáng] thích hợp nhất khi chụp ảnh
4 p |
362 |
236
-
HƯỚNG DẪN LỰA CHỌN MÁY ẢNH KỸ THUẬT SỐ
83 p |
269 |
134
-
Cách chọn độ nhạy sáng của máy ảnh
7 p |
235 |
127
-
Các chế độ đo sáng
13 p |
240 |
120
-
ISO - độ nhạy sáng của máy ảnh
7 p |
281 |
113
-
Độ nhạy sáng (ISO)
5 p |
214 |
84
-
Sử dụng chế độ bù sáng
5 p |
165 |
84
-
Làm chủ độ phơi sáng camcorder
5 p |
124 |
53
-
Ebook Bước đầu nghệ thuật nhiếp ảnh: Phần 2 - Nguyễn Nhưng
53 p |
261 |
48
-
Làm sao tránh hiện tượng mắt đỏ
6 p |
104 |
47
-
Độ nhạy sáng
10 p |
95 |
25
-
Ebook Xử lý ảnh bằng kỹ thuật số: Phần 2 - Đỗ Khánh Vân
80 p |
205 |
20
-
Chọn chế độ căn sáng máy ảnh số
3 p |
54 |
18
-
Kỹ thuật chụp ảnh-Ống kính đa tiêu cự và ống kính tiêu cự cố định- Nên chọn loại nào?
5 p |
69 |
17
-
Độ nhạy sáng của máy ảnh
4 p |
70 |
12
-
Giúp bạn lựa chọn camera an ninh
16 p |
51 |
11
-
Bí quyết sử dụng máy ảnh dưới nước
3 p |
54 |
9

Set-Cookie: TLDEVNamespace=ecqpricpcg587osr4bkmbh33r2; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# LUẬN VĂN TỐT NGHIỆP ĐIỆN TỬ CÔNG SUÂT, CHƯƠNG 8
Chia sẻ: Nguyen Van Dau | Ngày: | Loại File: PDF | Số trang:8
lượt xem 70
download
![](http://image1.tailieu.vn/document/thumbnail/2010/20100819/kentit/80x100/chuong_8_839.jpg)
##
LUẬN VĂN TỐT NGHIỆP ĐIỆN TỬ CÔNG SUÂT, CHƯƠNG 8
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Đây là mạch biến đổi điện áp một chiều DC1 sang điện áp một chiều DC2. DC2 DC1 Bộ Băm xung DC1 = 300VDC : điện áp một chiều không thay đổi và được nắn từ điện áp xoay chiều không đổi. DC2 là điện áp có giá trị trung bình thay đổi, tuỳ thuộc vào việc điều chỉnh núm chỉnh (VR) để thay đổi độ rộng xung kích cho SCR. Ứng với mỗi sự thay đổi này sẽ làm cho mạch thí nghiệm tạo ra một giá trị điện áp trung bình tương ứng, tải sẽ nhận giá trị...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: LUẬN VĂN TỐT NGHIỆP ĐIỆN TỬ CÔNG SUÂT, CHƯƠNG 8
- Chương 8: MAÏCH BAÊM XUNG TAÉT CÖÔÕNG BÖÙC BAÈNG ÑIEÄN AÙP. A. GIÔÙI THIEÄU : Ñaây laø maïch bieán ñoåi ñieän aùp moät chieàu DC1 sang ñieän aùp moät chieàu DC2. DC1 Boä Baêm xung DC2 DC1 = 300VDC : ñieän aùp moät chieàu khoâng thay ñoåi vaø ñöôïc naén töø ñieän aùp xoay chieàu khoâng ñoåi. DC2 laø ñieän aùp coù giaù trò trung bình thay ñoåi, tuyø thuoäc vaøo vieäc ñieàu chænh nuùm chænh (VR) ñeå thay ñoåi ñoä roäng xung kích cho SCR. ÖÙng vôùi moãi söï thay ñoåi naøy seõ laøm cho maïch thí nghieäm taïo ra moät giaù trò ñieän aùp trung bình töông öùng, taûi seõ nhaän giaù trò ñieän aùp trung bình DC naøy ñeå thay ñoåi ñaët tính taûi (thay ñoåi ñoä saùng ñoái vôùi taûi trôû thuaàn nhö boùng ñeøn, thay ñoåi toác ñoä n ñoái vôùi taûi laø ñoäng cô). Chính söï thay ñoåi naøy khi ño baèng dao ñoäng kyù seõ thaáy nhöõng daïng soùng khaùc nhau. B. MUÏC ÑÍCH VAØ YEÂU CAÀU CUÛA BAØI THÍ NGHIEÄM : Muïc ñích : Giuùp cho sinh vieân thí nghieäm : Naém ñöôïc nguyeân taéc ñoùng ,ngaét SCR baèng phöông phaùp ñieän aùp ngöôïc . Hieåu ñöôïc söï thay ñoåi ñieän aùp trung bình DC ôû ngoû ra cuûa maïch baèng caùch thay ñoåi xung kích ôû caùc cöïc coång G1,G2. Coù khaû naêng ñieàu khieån vaø phaân bieät ñöôïc caùc loaïi taûi : taûi trôû thuaàn, taûi caûm, taûi ñoäng cô thoâng qua daïng soùng ño ñöôïc . Ñeå coù cô sôû phaân bieät nhöõng öu khuyeát ñieåm cuûa maïch naøy vôùi caùc maïch, thay ñoåi ñieän aùp trung bình DC ôû ngoû ra, khaùc.
- Phaân bieät caùc daïng soùng theo lyù thuyeát vaø trong thöïc teá. Yeâu caàu : Sinh vieân thí nghieäm caàn chuaån bò tröôùc khi thí nghieäm: Veà kieán thöùc : Nhöõng phöông phaùp ñoùng ngaét SCR . Bieát caùch söû duïng dao ñoäng kyù. Phaân bieät caùc loaïi taûi . Naém vöõng nguyeân taéc an toaøn . Veà thieát bò : Daây noái . Dao ñoäng kyù. C. NGUYEÂN LYÙ HOAÏT ÑOÄNG CUÛA MAÏCH (HÌNH VI.2). Rt XK1 A R1 C S1 R2 D2 + R4 XK2 E=300V S2 R3 D1 L B Hình VI.2 Sô ñoà baêm xung taét cöôõng böùc baèng
- Maïch söû duïng hai SCR1 (kyù hieäu S1) vaø SCR2 (kyù hieäu S2), chuùng ñoùng (daãn) khi coù xung döông ñöôïc caáp ôû XK1 (xung kích 1). Trong maïch coù tuï ñieän C, D, L duøng ñeå chuyeån maïch. Khi nguoàn moät chieàu E ñaõ ñöôïc caáp, traïng thaùi ban ñaàu : S1 vaø S2 ñeàu bò khoaù (töùc chöa coù xung kích ôû cöïc coång) thì khoâng coù baát kyø moät doøng ñieän naøo chaïy qua taûi. Ñeå maïch hoaït ñoäng moät caùch hôïp lyù thì ñaàu tieân cho tuï C naïp baøng caùch cho xung ñieàu khieån vaøo cöïc coång cuûa S2, luùc naøy maïch ñieän hình VI.2 Rt S1 Rt S1 töông ñöông nhö hìnhVI.3: tuï ñieän C seõ ñöôïc naïp theo ñöôøng E_ Rt _+ C _ S2 _ E vaø doøng ic giaûm daàn theo haøm muõ töø giaù trò ñaàu C S2 + C S2 E/Rt . E E D1 L Hình VI.3 Hình VI.4 Caùc quaù trình chuyeån maïch. Sau moät khoaûng thôøi gian, tuï C ñöôïc naïp tôùi ñieän aùp E cuûa nguoàn, nhöng thöïc teá khi doøng ñieän taûi giaûm döôùi möùc duy trì cuûa S2 thì doøng ñieän ngöng. Khi coù xung ñieàu khieån vaøo cöïc coång cuûa S1, laøm S1 ñoùng maïch nhö hình VI.4, luùc naøy tuï C phoùng ñieän qua S1 - L –D1 – C vaø ñöôïc naïp ngöôïc laïi. Ñieän aùp treân tuï taêng daàn theo chieàu ngöôïc laïi vaø cuoái cuøng, ñieän aùp treân noù seõ laø uc = -E do coù söï xuaát hieän dao ñoäng LC. Dao ñoäng LC trong maïch seõ naïp vaøo tuï
- C vaø noù chæ keùo daøi trong moät nöûa chu kyø (vì D1 ngaên doøng ñieän ngöôïc). Luùc naøy neáu cho xung ñeå môû S2, thì S1 seõ chòu ñieän aùp ngöôïc uc = -E laøm S1 ngöng daãn (traïng thaùi chuyeån töø hình VI.4hìnhVI.3). Goïi chu kyø baêm laø T: T = T1+T2. Thôøi gian ñoùng maïch cuûa S1 laø T1 : T1 = T. Thôøi gian ngaét maïch cuûa S1 laø T2 =T –T1 vaø tyû soá chu kyø laø D = T1/T. Gía trò trung bình cuûa ñieän aùp taûi : DT 1 Ut T Udt DU 0 Baèng caùch laøm bieán ñoåi tyû soá chu kyø D (trong khi giöõ cho taàn soá khoâng ñoåi T=const) ta coù theå ñieàu chænh ñöôïc giaù trò trung bình cuûa ñieän aùp moät chieàu ñaët treân taûi. D. TIEÁN HAØNH THÍ NGHIEÄM . a. Trong tröôøng hôïp Rt laø taûi trôû thuaàn (boùng ñeøn) . 1. Laép maïch nhö hình veõ (Hình VI.2) 2. Noái cöïc döông cuûa nguoàn moät chieàu E (300V) vôùi ñieåm A, cöïc aâm vôùi ñieåm B cuûa maïch ñoäng löïc (Hình VI.2) 3. Noái G1, K cuûa maïch xung kích treân moâ hình vôùi cöïc G vaø cöïc K cuûa S1 cuûa maïch (Hình VI.2), töông töï noái G2, K vôùi cöïc G, K cuûa S2. 4. Maéc ñoàng hoà ño doøng noái tieáp vôùi taûi, ñoàng hoà aùp song song vôùi taûi. 5. Ñieàu chænh nuùm (VR) veà vò trí nhoû nhaát (min). 6. Kieåm tra maïch tröôùc khi baät nguoàn. 7. Baät nguoàn 300V vaø nguoàn taïo xung kích. Ñieàu chænh nuùm VR vaø choïn ra 3 vò trí khaùc nhau (töø min ñeán max), öùng vôùi moãi vò trí haõy:
- -Ghi nhaän caùc giaù trò doøng ñieän vaø ñieän aùp treân ñoàng hoà ño. ÖÙng vôùi moãi loaïi taûi haõy ghi treân moãi baûng nhö sau: Caùc vò trí chænh cuûa Möùc chænh Möùc chænh Möùc chænh VR VR1 VR2 VR3 Giaù trò doøng ñieän ñoïc ñöôïc treân ñoàng hoà. Giaù trò ñieän aùp ñoïc ñöôïc treân ñoàng hoà. -Duøng dao ñoäng kyù ñeå ño vaø veõ daïng soùng ñieän aùp, doøng ñieän vaøo caùc hình döôùi ñaây taïi caùc vò trí sau : Ghi chuù : ño daïng soùng doøng ñieän chính laø ño daïng soùng ñieän aùp treân caùc ñieän trôû töông öùng. Treân taûi:ut , it +2E E t 0 -E -2E Baûng 1: veõ daïng soùng ñieän aùp vaø doøng ñieän treân taûi. Giaûi thích söï khaùc nhau cuûa daïng soùng treân taûi taïi 3 vò trí ñaõ choïn cuûa nuùm chænh (VR).
- uc ,ic +2E Treân tuï: E t 0 -E -2E Baûng 2: veõ daïng soùng ñieän aùp vaø doøng ñieän treân tuï Giaûi thích söï khaùc nhau cuûa daïng soùng treân tuï taïi 3 vò trí ñaõ choïn cuûa nuùm chænh u Treân S1, S2 (VR). : us1 ,us2 +2E E t 0 -E -2E Baûng 3: veõ daïng soùng ñieän aùp treân S1vaø S2. Giaûi thích söï khaùc nhau cuûa daïng soùng treân S1, S2 taïi 3 vò trí ñaõ choïn cuûa nuùm chænh (VR). Tr is1 ,is2 +2E E t 0
- Baûng 4: veõ daïng soùng doøng ñieän treân S1vaøS2. Caên cöù vaøo daïng soùng ño ñöôïc haõy so saùnh giaù trò ñieän ñoïc ñöôïc treân ñoàng hoà vôùi giaù trò tính baèng coâng thöùc sau: Giaù trò trung bình cuûa ñieän aùp taûi : DT 1 Ut T Udt DU 0 T T0 T0 D Trong ñoù D : tyû soá T chu kyø U = E = 300V. Hình VI.5 Daïng soùng baêm xung b. Thay taûi trôû thuaàn Rt baèng taûi caûm. Tieán haønh thí nghieäm töông töï nhö caùc böôùc 2 ñeán 8 ôû treân. c. Thay taûi trôû thuaàn Rt baèng taûi ñoäng cô. Tieán haønh thí nghieäm töông töï nhö caùc böôùc 2 ñeán 8 ôû treân. Chuù yù : nhôù maéc diode D2 vaøo maïch nhö hình veõ ñoái vôùi taûi caûm vaø taûi ñoäng cô. E. Caâu hoûi : 1. Taïi moãi vò trí giaûi thích söï khaùc nhau veà daïng soùng dieän aùp treân taûi cuûa 3 loaïi taûi : taûi trôû thuaàn, taûi caûm, taûi ñoäng cô.
- 2. So saùnh giaù trò ñieâïn aùp vöøa tính vôùi giaù trò ñoïc ñöôïc treân VOM. 3. Maïch treân SCR ñoùng ngaét baèng phöông phaùp naøo ? Caên cöù vaøo maïch ñaõ laép ñeå giaûi thích. 4. Hieän töôïng gì xaûy ra khi maát xung kích S1? 5. S1 vaø S2 khi taûi hoaït ñoäng, linh kieän naøo chòu doøng nhieàu hôn?.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Điều khiển tốc độ động cơ 3 pha lồng sóc bằng biến tần
52 p |
467 |
245
-
LUẬN VĂN TỐT NGHIỆP ĐIỆN TỬ CÔNG SUÂT, CHƯƠNG 3
10 p |
234 |
123
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Thiết kế cung cấp điện cho phân xưởng sửa chữa cơ khí
69 p |
206 |
92
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Tìm hiểu về dây chuyền sản xuất điện năng trong nhà máy nhiệt điện Uông Bí 2, đi sâu nghiên cứu thiết bị điện hệ thống tuabin máy phát
63 p |
152 |
71
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Tìm hiểu quy trình vận hành thiết bị điện trong nhà máy nhiệt điện
77 p |
118 |
50
-
Đồ án tốt nghiệp: Xây dựng thư viện điện tử công suất và truyền động điện trên Matlab
49 p |
105 |
47
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Thiết kế giao diện kết nối giữa WinCC và step7 trong công đoạn đập đá vôi nhà máy XMHP
96 p |
95 |
46
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Thiết kế cung cấp điện cho phân xưởng sửa chữa cơ khí của Công ty cổ phần tư vấn đầu tư và xây lắp Hải Sơn
87 p |
104 |
39
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Nghiên cứu vấn đề điều khiển lò nhiệt. Đi sâu xây dựng chương trình giám sát nhiệt độ lò nhiệt trong phòng thí nghiệm sử dụng card PCI 1710
63 p |
81 |
37
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Tổng quan quá trình sản xuất cáp điện của công ty Ls-Vina Cable. Đi sâu nghiên cứu hệ thống điều khiển máy bện cáp 54-Bobin No2
78 p |
90 |
34
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Nghiên cứu hệ thống điều khiển tự động chế biến than nhà máy nhiệt điện Uông Bí
97 p |
63 |
28
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Trang bị điện - điện tử cần trục 120 tấn nhà máy đóng tàu Bạch Đằng. Đi sâu nghiên cứu cơ cấu nâng hạ hàng và cơ cấu tầm với
70 p |
92 |
27
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Nghiên cứu thiết kế và xây dựng hệ thống truyền động điện động cơ một chiều điều chỉnh tốc độ dùng bộ điều khiển vạn năng sử dụng vi điều khiển PSOC
51 p |
69 |
20
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Nghiên cứu hệ thống phát điện đồng trục trên tàu thủy sử dụng máy điện dị bộ nguồn kép
77 p |
51 |
20
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Nghiên cứu tổng quan về MicroSmart và sản phẩm hãng IDEC. Ứng dụng MicroSmart điều khiển hệ thống nhiều bơm tự động lên bể hở
89 p |
60 |
17
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Thiết kế cung cấp điện cho Công ty Đóng tàu Phà Rừng
64 p |
52 |
16
-
Đồ án tốt nghiệp Điện tự động công nghiệp: Xây dựng mô hình bộ chấn lưu điện tử sóng chữ nhật tần số thấp điều khiển số với mạch điều khiển cộng hưởng và vòng công suất
74 p |
50 |
10

Set-Cookie: TLDEVNamespace=3toidnc3kkafggpm01ipg5heh0; path=/; domain=.tailieu.vn; HttpOnly