Visų grafo tiltų radimas Grafo uždavinio sprendimas


Informatikos kursinis darbas. Užduoties analizė. Programos tekstas. Išvados. Literatūros sąrašas.


Kadangi viena jungioji komponentė rodo kad yra vienas grafas, jei yra daugiau jungiųjų komponenčių, vadinasi grafas yra nejungus. Trindami atskiriam kiekviena briauna, per nauja ieškoma jungiųjų komponenčių skaičius, palei tai, jei yra daugiau nei vienas, vadinasi radom tilta, ir taip sukam ciklą kol apeinamos visos briaunos. Skaičius (TiltuSkaicius) lygus nuliui ir paruošiama briaunų matrica (TiltoBriauna).

Kad programa veiktu sėkmingai, reikėjo įterpti (if) sąlyga, kad praleistu pirmąją paiešką, nes duotasis grafas gali turėti daugiau nei viena jungumo komponente, gali būti medis ir t.t...

%U = [1 2; 1 4; 2 4; 4 5]; % Briaunu matrica

U = [1 2; 1 5; 5 4; 6 3; 3 5; 3 1]

ilgis = length(U(:, 1)); % Randa kiek yra briaunu, ji daudosima cikle while

m = length(U(:, 1)); % Randa kiek yra briaunu, ji naudosime tolesniuose veiksmose

Uždavinys išspręstas pasinaudojant jungiųjų komponenčių radimo algoritmu, bei pridėjus tam tikrus ciklus ir reikalingus kintamuosius. Nepaisant įvairių grafo tipų, programa veikia teisingai, buvo rasti visi tiltai ir jų briaunos, jei jų nerasta tai išspausdina Tiltu skaicius: 0, Tiltu Briaunos: Tilto briaunu nerasta.

  • Informatika Kursiniai darbai
  • 2015 m.
  • Lietuvių
  • 6 puslapiai (872 žodžiai)
  • Universitetas
  • Informatikos kursiniai darbai
  • Microsoft Word 91 KB
  • Visų grafo tiltų radimas Grafo uždavinio sprendimas
    10 - 4 balsai (-ų)
Visų grafo tiltų radimas Grafo uždavinio sprendimas. (2015 m. Rugsėjo 08 d.). http://www.mokslobaze.lt/visu-grafo-tiltu-radimas-grafo-uzdavinio-sprendimas.html Peržiūrėta 2016 m. Gruodžio 03 d. 06:52