Management Teoria transmisiunii informatiilor Biologie Didactica Mecanica Literatura comparata Arheologie industriala Politologie Ergoterapie Istoria secolului XX Logopedie CIA Fiscalitate Chimie Informatica AutoCAD Fizica Logistica Marketing Oracle EXPERT ACHIZITII PUBLICE Marketing Psihologie Educationala transporturi Gestiune hoteliera Arhitectura peisagera Comert IS Economia si Gestiunea Intreprinderii I I T M Diverse Transmisiuni Analogice si Digitale. Structuri de date si algoritmi C++ Sociologia Comunicarii in Masa Prelucrarea semnalelor si imaginilor Finante Analiza matematica Algoritmi si programare Metodologie si Statistica Introducere in istoria dreptului Analiza economico financiara Constructii Metodologie Psihologie Cibernetica Electronica industriala Drept constitutiv Comunicare Teoria Sistemelor Frigotehnie Baze de Date Drept comercial Contabilitate Administratie Publica Depanare PC Sociologie Franceza Automatica Drept penal Credit si banci Relatii internationale Ginecologie Drept european Drept Filosofie Istoria literaturii romane Dreptul familiei Educatie fizica si sport Radiologie Pedagogie Sociala Statistica Turism Pedagogie Moneda Credit Istorie Dispozitive si Circuite Electronice Asistenta Sociala Retele de calculatoare SPICE Word Merceologie Drept civil Materiale in electronica Engleza Spectroscopie si LASERI Psihiatrie Visual Basic Consiliere scolara Electronica Mass media Terapia ocupationala si ergoterapia Kinetoterapie Semiotica Medicina Economie Istoria dreptului Managementul resurselor umane Bazele Managementului Industrial Sociologia familiei Limba Romana Circuite digitale integrate Criminalistica Geografie Hidrologie Drept constitutional Contabilitate bancara Astrologie Istoria relatiilor internationale MANAGER DE PROIECT Drept Penal Special Drept economic Programare orientata pe obiecte Relatii Internationale si Studii Europene Teologie Drept administrativ Economie politica Asistenta medicala Internet Fotografia digitala Inginerie mecanica Drept roman Muzica Arhitectura Circuite Integrate Astronomie Bazele Sistemelor de Achizitie a Datelor Protectia Mediului PHP si SQL Prelucrarea si Analiza Imaginilor Matematica SPSS Genetica Psihopedagogie Speciala Agricultura Java

Algoritmica

Publicat: 05 Iul 2011 00:00

Teoria grafurilor, la inceputurile ei, s-a dezvoltat paralel cu algebra. Grafurile au multiple aplcatii practice, fiind strans legate de multe ramuri ale matematicii (cercetari operationale, teoria grupurilor, teoria numerelor), dar sunt folosite si ca modele matematice in rezolvarea unor probleme tehnice, economice, etc. Studiul grafurilor isi are originea in lucrarile lui Euler din 1736, in care studia problema podurilor de la Königsberg.

Orasul Königsberg se afla aproape de punctual de varsare a raului Pregolea in Marea Baltica. Raul are pe teritoriul orasului doua brate confluente iar in punctual de confluenta se afla o insula, numita “Curtea Hanului”1. Aceasta insula este legata de maluri prin cinci poduri. Peste fiecare brat al raului mai exista cate un pod. Problema care a aparut cerea sa se gaseasca un traseu continuu care sa treaca o singura data pe fiecare din cele sapte poduri.(vezi figura 1.) Euler a fost primul care a aratat ca aceasta problema nu are solutie.

Prima carte de teoria grafurilor a fost publicata de D. König in 1936, Theorie der endlichen und unendlichen Grphen, urmata de cartea lui C. Berge in 1957 Théorie des graphes et ses applications. Fie X o multime finita nevida, X={x1, x2 ,…,xn }. Se numeste graf o pereche G = (X, U) formata din multimea X de varfuri sau noduri si din multimea U={u1, u2, …, um } de perechi de varfuri numite arce sau muchii. Reprezentarea grafurilor poate fi facuta in diferite moduri in functie de cine este “utilizatorul”. Daca este calculatorul, este de preferat ca graful sa fie dat cu ajutorul matricei sale de adiacenta.

Altfel, oamenii, prefera vizualizarea grafului sub forma unei colectii de puncte legate prin linii, ceea ce implica darea unor informatii geometrice despre graf. Cardinalul multimii X, se noteaza |X|, si se numeste ordinul grafului G. in cele ce urmeaza vom lucra numai cu grafuri finite. in multimea U putem avea mai multe perechi identice. Daca numarul lor nu depaseste un numar natural q, spunem ca G este un q-graf

Un 1-graf se mai numeste si graf orientat. in aceasta situatie U este o submultime a produsului cartezian XX×. Atunci orice element este o pereche ordonata, de forma Uu∈),,(yxu=cu Xyx∈,si il numim arc. Varful x se numeste extremitatea initiala iar varful y se numeste extremitatea finala. in acest caz varfurile x si y se numesc adiacente.


Fie X o multime finita nevida, X={x1, x2 ,…,xn }. Se numeste graf o pereche G = (X, U) formata din multimea X de varfuri sau noduri si din multimea U={u1, u2, …, um } de perechi de varfuri numite arce sau muchii. Reprezentarea grafurilor poate fi facuta in diferite moduri in functie de cine este “utilizatorul”. Daca este calculatorul, este de preferat ca graful sa fie dat cu ajutorul matricei sale de adiacenta. Altfel, oamenii, prefera vizualizarea grafului sub forma unei colectii de puncte legate prin linii, ceea ce implica darea unor informatii geometrice despre graf.

Cardinalul multimii X, se noteaza |X|, si se numeste ordinul grafului G. in cele ce urmeaza vom lucra numai cu grafuri finite. in multimea U putem avea mai multe perechi identice. Daca numarul lor nu depaseste un numar natural q, spunem ca G este un q-graf

Un 1-graf se mai numeste si graf orientat. in aceasta situatie U este o submultime a produsului cartezian XX×. Atunci orice element este o pereche ordonata, de forma Uu∈),,(yxu=cu Xyx∈,si il numim arc. Varful x se numeste extremitatea initiala iar varful y se numeste extremitatea finala. in acest caz varfurile x si y se numesc adiacente.

Trebuie sa citesti

Ce presupune ingrijirea unei peruci Belher
Ce presupune ingrijirea unei peruci Belher

Purtarea unei peruci a devenit un trend, una din solutiile ingenioase pentru o schimbare de look rapida si de efect. Desi avem tendinta sa asociem peruca cu lipsa parului si automat cu anumite probleme de sanatate, in unele cazuri posesoarele de peruci sunt doar impatimite ale schimbarilor

Sanatatea porumbeilor voiajori, sustinuta prin solutii profesionale de la ProduseColumbofile.ro
Sanatatea porumbeilor voiajori, sustinuta prin solutii profesionale de la ProduseColumbofile.ro

Cresterea porumbeilor voiajori este o activitate pe cat de interesanta, pe atat de solicitanta. Grija acordata ingrijirii lor, curatirii mediului in care cresc, precum si alimentatiei nu are timp de repaos. La toate acestea, columbofilii trebuie sa adauge si controalele periodice, respectiv

Ce poti face la Budapesta intr-o singura zi
Ce poti face la Budapesta intr-o singura zi

O zi la Budapesta este o experienta pe care merita sa o incerci oricand. Cu siguranta te va convinge sa revii pentru a descoperi mai pe indelete acest oras cu arhitectura impresionanta si in care fiecare coltisor pare sa spuna o poveste. Impartita in doua de Dunare, Budapesta a devenit un oras

Criteriile de selectie ale unui motocultor
Criteriile de selectie ale unui motocultor

Ce sunt motocultoarele? Motocultorul este  o masinarie agricola ce poate sa prelucreze terenurile agricole. Este alimentat la priza si are capacitatea de a fi dotat cu mai multe accesorii. Cu ajutorul motouneltei si accesoriilor se poate realiza o gama larga de activitati. Atunci cand cumperi

De sarbatori nu uitam de distractia celor mici
De sarbatori nu uitam de distractia celor mici

In toata agitatia acestei luni, cu pregatirile specifice pentru Craciun, adultii nu trebuie sa uite de distractia celor mici. Petrecerile pentru copii au devenit o moda si, mai mult decat a urmari un trend, este vorba despre bucuria adusa celor mici. Paradisul Personajelor vine cu un pachet de

Teste Online

Comunica liber

Comunica liber.Nu fi suparat.Ai cu cine comunica

mai multe »
Acest site foloseste Cookie-uri.
Folosim cookie-uri pentru a personaliza continutul si reclamele, pentru a oferi caracteristici specifice retelelor sociale si pentru a analiza traficul nostru. De asemenea, impartasim informatii despre felul in care ne utilizati site-ul, cu partenerii nostri de pe retelele sociale, de publicitate si de statistica in conformitate cu Politica de confidentialitate. Va puteti administra preferintele in Setari cookie.