Граф (математика)

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Емблема за пояснителна страница Вижте пояснителната страница за други значения на Граф.

Диаграма на неориентиран граф със шест върха и седем ребра

Граф (мн. ч. Графи) е термин от математиката, с който се означава наредена двойка G=(V,E), където

  • V е множество от елементи, наречени върхове,
  • E е множество от двучленни подмножества на V, т.е. E ⊆ V×V. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ребра или още ръбове на графа, а той от своя страна — неориентиран (ненасочен) граф. Когато тези двойки са наредени, елементите на Е се наричат дъги, а графът Gориентиран (насочен) граф.

Основни понятия[редактиране | edit source]

Граф, множеството от чиито върхове е празното множество, се нарича нулев граф. Естествено, за него и множеството от ребрата също е празното множество. Друг тривиален случай е налице, когато множеството от върховете на графа се състои само от един елемент. И в този случай множеството на ребрата е празно.

Когато в графа G=(V,E), E е съвкупността от всички двойки елементи на множеството V, т.е. всеки два върха на графа са свързани с ребро, то G се нарича пълен граф.

Нека са дадени два графа G1=(V,E1) и G2=(V,E2), за които са в сила следните три условия:

  • множествата на върховете съвпадат,
  • двете множества от дъги са непресичащи се, т.е. E1 ∩ E2 = ø, и
  • графът G=(V, E1 ∪ E2) е пълен граф.

Тогава, графите G1 и G2 се наричат взаимнодопълнителни или се казва че графът G2 е допълнителен на графа G1.

Нека са дадени два графа G1=(V1, E1) и G2=(V2, E2). Ако е в сила V1 ∩ V2 = ø, то двата графа се наричат дизюнктивни или чужди. Ако за тях е едновременно в сила V1 = V2, E1 = E2, то двата графа се наричат идентични, в противен случай двата графа са различни.

Графите биват крайни и безкрайни и разграничението между тях е от съществено значение в теорията на графите. Краен граф е онзи, за който и V, и E са крайни множества.

Крайният неориентиран граф G=(V,E) можем да превърнем в краен неориентиран мултиграф, когато позволим повече от едно ребро да свързва два връха на графа.

Нека са дадени два графа G1=(V1, E1) и G2=(V2, E2) такива, че V1 ⊂ V2 и E1 ⊂ E2. При тези допускания графът G2 се нарича подграф на G1. За всеки граф от особено значение са онези негови подграфи, които съдържат същото множество върхове.

Две ребра от се наричат инцидентни, ако имат общ връх. Два върха се наричат съседни, ако са свързани с ребро, т.е. образуват двойка от множеството Е.

Друго основно понятие при графите е степен на връх. Това е броят на всички ребра, които са инцидентни с върха. Връх със степен 0 обикновено се нарича изолиран. Граф, на който всички върхове са от една и съща степен, се нарича регулярен или още правилен.


Източници[редактиране | edit source]

  • Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 1967
  • Красимир Манев, „Увод в дискретната математика“, издателство КЛМН, София, 2003, ISBN 954-535-136-5

Външни препратки[редактиране | edit source]