Образец материалов для подготовки преподавателей к лекции

Ta’rif. Graf ning qisman grafi deb ataladi, agarda u berilgan grafning barcha uchlariga ega bo’lib, ammo barcha qirralariga ega bo’lmasa, balki qisman qirralariga ega bo’lsa, ya’ni

•  

The Concept of Degree

• The Concept of Degree
• The degree of a vertex is the number of endsegments of edges that “sticko ut of” the vertex. We will show that the sum of the degrees of all the vertices in a graph is twice the number of edges of the graph.

Hech qanday qirraga “insindent” bo’lmagan uch ajratilgan uch deyiladi. Agar grafda shunday uchlar bo’lsaki ular ikki va undan ko’p uchlar bilan birlashtirilgan bo’lsa bunday graf multigraf deyiladi. Ushbu uchga tegishli bo’lgan qirralar soni uchning darajasini belgilaydi. 2.6rasmda ko’rsatilgan x2 uch 6 darajaga ega, chunki unga α1, α2, α3, α4, α5, α6, α7 , qirralar “insindent”dir, x1 uchning darajasi 3, x4 ning darajasi esa 1.

Definition

• Definition
• LetG beadirectedgraphwithorderedverticesv1,v2,...,vn.Theadjacencymatrix of G is the n × n matrix A= (aij) over the set of nonnegative integers such that aij =the number of arrows from vi to vj for all i, j =1,2,...,n.

• Matritsa ustunlari va qatorlari graf uchlarini nomerlariga mos keladi, uning elementi cn x1 va xj birlashtiruvchi qirralar sonidir. 2.6.graf uchun matritsa quyidagi ko’rinishga egadir.

Observe that G$ is a different graph from G (for instance, in G the endpoints of e1 are v1 and v2, whereas in G$ the endpoints of e1 are v1 and v3). Yet G$ is certainly very similar to G. In fact, if the vertices and edges of G$ are relabeled by the functions shown in Figure 10.4.3, then G$ becomes the same as G.

• Observe that G$ is a different graph from G (for instance, in G the endpoints of e1 are v1 and v2, whereas in G$ the endpoints of e1 are v1 and v3). Yet G$ is certainly very similar to G. In fact, if the vertices and edges of G$ are relabeled by the functions shown in Figure 10.4.3, then G$ becomes the same as G.

• graflar faqat nomerlash bilan farqlanadigan bo’lsa, ular chizilishda farqlanib, bu holda matritsa grafni izomorfizmgacha bo’lgan aniqlikda belgilaydi deymiz. Bunday graflar izomorf graflar deyiladi.
• Graf (tekis) planar deyiladi, agarda ushbu grafga izomorf bo’lgan grafni tekislikda qirralari kesishmagan holda tasvirlash mumkin bo’lsa.

Ta’rif. Siklga ega bo’lmagan bog’langan graf daraxt deb ataladi, uning qirralari esa shoxlaridir. n-uchli daraxtda (n-1) ta qirra border. (2.14-a rasm) Haqiqatdan ham, agarda daraxtning ikki uchuni birlashtiruvchi bitta qirra qo’shilsaa, grafda sikl paydo bo’ladi.(2.14-b rasm). Agar bir qovurg’ani olib tashlasa, graf bog’lanmagan bo’lib qoladi.

Planar graphs

• Planar graphs

An undirected graph is called a planar graph if it can be drawn on a paper without having two edges cross.

We say that a graph can be embedded in the plane, if it planar. A planar graph divides the plane into regions (bounded by the edges), called faces. The following planar graph has 4 faces.