基于图论和集合理论模型的信息通信网络结构综合方法(IJISA-V9-N11-6)

I.J. Intelligent Systems and Applications, 2017, 11, 42-51

Published Online November 2017 in MECS (https://www.wendangku.net/doc/4d15121147.html,/)

DOI: 10.5815/ijisa.2017.11.06

The Method of Variant Synthesis of Information and Communication Network Structures on the Basis of the Graph and Set-Theoretical Models

Vadym Mukhin

National Technical University of Ukraine "Kiev Polytechnic Institute", Kiеv, Ukraine

E-mail: v_mukhin@i.ua

Yury Romanenkov and Julia Bilokin

National Aerospace University "Kharkiv Aviation Institute", Kharkiv, Ukraine

E-mail: KhAI.management@https://www.wendangku.net/doc/4d15121147.html,; juliabelokon84@https://www.wendangku.net/doc/4d15121147.html,

Anton Rohovyi and Anna Kharazii

National Technical University "Kharkiv Polytechnic Institute", Kharkiv, Ukraine

E-mail: npk.asystems@https://www.wendangku.net/doc/4d15121147.html,; haraziy@https://www.wendangku.net/doc/4d15121147.html,

Viktor Kosenko

SE "Khark?v Scientific-Research Institute of Mechanical Engineering Technology", Kharkiv, Ukraine

E-mail: kosvv@ukr.ua

Nataliia Kosenko

O. M. Beketov Kharkiv National University of Urban Economy, Kharkiv, Ukraine

E-mail: kosnatalja@https://www.wendangku.net/doc/4d15121147.html,

Jun Su

School of Computer Science, Hubei University of Technology, Wuhan, China

Received: 03 July 2017; Accepted: 17 September 2017; Published: 08 November 2017

Abstract—The subject matter of the article is developing information and communication network (ICN) for critical infrastructure systems (CIS). The aim of the work is to provide high-quality information and telecommunication processes by developing the optimal version of distributing CIS functional tasks and ICN processes to the network nodes. The article deals with following problems: developing a model for mapping the information and technical ICN structures, developing a method for variant synthesis of ITS structural models, a formalized representation of the problem of selecting CIS optimal structure. The methods used are: the system method, the set-theoretic and graphic analytic approaches, methods of hierarchic structures synthesis, optimization methods. The following results were obtained: the use of system approach for formalizing the information processing process in CIS was justified; mapping the ICS functional system into the information and technical one was presented as multilevel graph chain; the generalized representation of graph structures hierarchy was developed for the set of data transmitting tasks; this approach enabled formal representing alternative variants that consider the main links, sequencing, the amount and flows of the processed information among the different structure levels; the scheme of variant synthesis method of ICN models according to graph structures mapping was developed; the problem of selecting optimal ICN structures was formally presented; a complex efficiency criterion for solving problems of optimizing variant synthesis of structures; the problem of optimal synthesis of the structure of the given level factored in resource constraints was formulated. Conclusions. The article deals with such novelty aspects as improving the model of problem of selecting the optimal ICN structure by set-theoretic formalization factored in the criterion of maximum intensity of computational resource application, which enabled determining structural links among the major elements considering the decomposition of the model up to the basic elements such as "node" and "task" and the development of a new method of optimal ICN structuring which unlike the existing ones involves the variant synthesis of structures hierarchy and formalizing selection problems on the basis of set-theoretic models, which enables providing the efficiency of application of information and technical net resources. Index Terms—Information and communication network, structure synthesis, graph representation, selecting,

mapping, set-theoretic model, software.

I.I NTRODUCTION

With the development of high technologies, the range of high-risk facilities that belong to the class of critical infrastructure systems (CIS) is expanding. For example, thermal, nuclear and hydroelectric power stations, high-speed ground and air transport, defense and space systems. The challenge for such systems is to provide quality information and telecommunications processes. In the context of continuously improving concepts of developing information and communication networks (ICN), in the face of new network technologies, there is the tendency of their "convergence", i.e. amalgamating into more complex structures and technologies. There is the convergence of infomedia different in origin and operation principles.

Despite the rapid development of physical and channel-level technologies, the full potential of ICN can be realized only due to effective managing available network resources in the face of increasing demands for the operability of information exchange. This determines the necessity of searching new approaches to determining the physical and functional structures of the network.

II.P ROBLEM A NALYSIS AND S ETTING THE P ROBLEM When building distributed and local information and communication networks, there is a number of unresolved problems which are complex scientific and technical issues. Considering the ICN hardware and software these problems can be grouped to:

- develop a reliable ICN on the basis of available hardware and software that now consist of isolated

and unequal components;

- turn to promising technical and software tools step by step.

At the first stage, when installing software complexes on separate ICN fragments, it is necessary to distribute CIS functional tasks to the nodes of the base fragment, taking into account the heterogeneity of the nodes, the heterogeneity and inequality of hardware and software.It is necessary to keep in mind that the requirements of operability, reliability, continuity and completeness of information for these systems are of primary importance.

[1]

Many publications deal with the analysis and synthesis of ICN [2 – 7]. The classical mathematical models based on the results of graph theory and the theory of mass service [3] do not take into account the dependence of net structure characteristics on the parameters of applied problems that are solved in a networked environment, which leads to a loss of accuracy in the results of modelling.

The analysis of the literature showed that the majority of the mathematical models that assume the operation of software complexes in a multiservice network environment do not take into account the heterogeneity of the basic hardware and software support tools of the ICN [6 – 9].

One of the promising areas of ICN development is the service-oriented approach that enables investigating the processes of information exchange among the network nodes involved in solving various functional tasks and supporting various information processes. This approach enables more adequate modelling of data flows in multiservice ICN. However, the formalization presenting data streams in this approach is still insufficient and is limited to modelling individual tasks and aspects of ICN operation [10, 11].

Therefore, the purpose of this article is to develop a formalized model and a method for synthesizing ICN structures that enables developing an optimal version of distributing CIS functional problems and ICN processes to the nodes of the basic fragment of the network.

III.P ROBLEM S OLVING

A large number of elements of CIS subsystems and the functions they perform, a high degree of elements interconnection, the complexity of algorithms for selecting particular actions for controlling real-time processes, large amounts of processed information determine ICN that enables CIS operating as a complex system [8]. The synthesis of the structure of a complex system requires developing the following formalized models;

а) he models of the controlled system structure for determining the optimal composition and

interrelations of the systems elements, the optimal

partitioning of the set of controlled objects into

separate subsets that have the specified

characteristics of the relations;

b) the model of the control system structure for

solving the problems of variant choice: a number

of levels and subsystems, the organizational

hierarchy, for determining the principles of

management organization and the optimal

distribution of performed functions among

different system components;

c) the model of the structure of data transmission and

processing systems factored in the composition of

the hardware and software of the

telecommunications network.

When developing a model for the hardware and software structure, it is necessary to consider the following points [8, 12, 13]:

- determining a set of ICN nodes and connections among them;

- distributing tasks assigned to the technical means of ICN to the levels and nodes of the system;

- selecting ICN technical means that provide the effective solution of CIS tasks.

are solved with the help of a set of system and application software. Accordingly, at the next level, for each element i I

∈ there is a graph P P

G(P,Г)

= of a set of elements of the used software (SW) k p P,k1,l

∈= ; PГ is a set of arcs that show the relationships between them. Mapping the set of vertices of the graph j i I,j1,m

∈= in a set of vertices k p P,k1,l

∈=, I P

G G

→ is obtained. The graph of a set of information support elements (specialized and local databases) is denoted as

B B

G(B,Г)

=, where В is a set of vertices of the graph corresponding to the elements of information support; B

Г is a set of arcs reflecting data relationship. Mapping a set of vertices of the graph k p P,k1,l

∈= in a set of vertices m

b B,m1,f

∈=, P B

G G

→ of functional structure in ICN information structure is obtained. This mapping implements ICN information structure (IS). Thus, mapping

()()

S I P B IS

FS

G G G G

→→→

is formally represented as a multilevel chain of graphs mapping.

To implement information and communication tasks, ICN technical structure should be developed. Graphs U U

G(U,Г)

= that are the variants of realization of the local networks structure are defined as ICN nodes, where U is a set of vertices of the graph corresponding to the nodes of the network; U

Г is a set of arcs reflecting the system of switching nodes. Mapping a set of vertices of the graph j i I,j1,m

∈= in a set of vertices c

u U,c1,d

∈=, I U

G G

→ is obtained.

For a variety of options for ICN technical structure a variety of options for data transmission, that is traffic management, [16, 17] should be determined. Graph T T

G(T,Г)

= i.e. the options for implementing data flows as information links, where T is a set of vertices of the graph corresponding to the nodes of the network, and T U

?; U

Г is a set of arcs representing the system of knot commutation, T U

ГГ

?. Mapping the set of vertices of the graph c u U,c1,d

∈= in a set of vertices h

t T,h1,z

∈=, U T

G G

→ is obtained. This mapping implements ICN technical structure (TS).

Mapping ICN functional structure in the information and technical one is represented as a multilevel chain of graphs:

()

()

()

P B IS

S I FS

U T TS

G G

G G

G G

→

→→

→

After the synthesis of the options for ICN technical structure, the software and information support should be assigned to the nodes of the network factored in the channels of information interaction. The result can be

represented as a mutual mapping of the following sets: P U G G ? is options for assigning application programs to network nodes for solving specific functional tasks;

B T G G ? is definition of data flows at a variety of information relationships.

Taking into account the mappings mentioned above, which can be generally represented by functions φ1 … φ6, graph model of the synthesis of ICN structures looks as follows:

()

()

()

3124P

B

IS

S

I

5

6

FS

U

T

TS

G

G G

G G

G ?

?

?

?

??→??→??→

????→

In particular, for a complex of data transfer tasks, a

generalized representation of the graph structures hierarchy is shown in Figure 1. Here, set S represents the structure of probable realizations of CIS basic functional problems. Consequently, for each variant of implementation S, different variants of numerous dataware and software tasks, application programs and databases, as well as ICN nodes and data transmission facilities are considered.

According to the system approach, the scheme of the method of variant synthesis of ITS structural models as described by mapping graph structures (Fig. 1) is schematically shown in Fig. 2.

Fig.1. Generalized representation of the hierarchy of ICN

graph structures.

Fig.2. Scheme of the method of variant synthesis of ICN Structural models

It should be noted that, the relationships that reflect the sequence, amounts or flows of transmitted information are considered while formalizing the relationships between tasks or stages.

The system approach assumes that when the formalization of the process of information processing in a complex system changes to the model of its functioning, the following stages should be necessarily performed:

- modelling all admissible variants of initial data

allocation;

- modelling all variants of task placement among the system nodes;

-

distinguishing and analyzing partially isolated components of the system and constructing appropriate models.

According to the above scheme of the method the initial sets are represented in the mentioned models by the elements of the graph structures S, I, P, B, U, T; while mappings that determine the relationships of the structures as:

1S I

2I P U 3P B 4U T 5P U 6B T

:G G :G (G ,G ):G G :G G :G G :G G ?→?→?→?→????

Considering these mappings, the problem of selecting ICN optimal structures can be formally represented.

The elements of the graph structures I,J,L,M,P considered above are greater and include tasks, software, data, technical objects, communication facilities, etc. However, the above graph of alternative structures assumes such hierarchical sequence of the elements of structures where the subsets of homogeneous objects are detailed at the same level of hierarchy.

In such a case the correspondence which is important for the synthesis of structures should be set up among them, considering one of the two options:

- distinguishing such a variant (among the set of

admissible variants) that will enable achieving the required properties in the context of specified criteria

for optimality grounding

on a set

of required properties of the structure;

-

analyzing

the probability

of achieving ICN

required properties grounding on characteristics of

the structure.

In consideration of

the foregoing, ICN

information structure

can be

determined by a

set of

the

following

parameters:

- -

- - -

Besides, it is necessary to determine:

- - -

c) a set of descriptions of data amounts –Akm, which

are necessary for system applications while using them by specific tasks, and consist of matrix lines of data amounts Vk and Bk;

d) the matrix of system application assignment to the

net nodes – G;

e) the matrix of connecting users to the nodes – H; f) the matrix of databases allocation to the nodes – S.

This set definitely determines the information structure of an information and communication net.

Let us specify a set of parameters that determine the net information structure as SI. Thus, we have:

{}i km SI N,M,D,L,R,S ,A ,G,H,S =, i i i i i S {p ,d ,u ,W }=, km km km A {v ,b }=.

The major elements of the information structure and their parameters are shown in Fig. 3.

tasks

network nodes

Fig.3. The diagram of the major element and parameters of the model of ICN information structure

It should be noted that if system applications and databanks are compared according to their allocation to the net nodes (the rules of developing G and S matrices), databanks can be considered as system applications in the context of theoretical studies of the network. This approach enables simplifying the obtained data greatly and making them more descriptive.

Keeping in mind that all possible variants of the information structure of the network can be described in the foregoing manner, it is necessary to formalize the procedure for selecting the optimal structure, which is a sequence of particular selection problems.

Let a set of variants of ICN representation be denoted as:

{}011ik S (S ,S ),S s ,i 1,m,k 1,m ====

where 0S is the initial state of the model, which is determined by the functional tasks of the entire system; ik s is the state of the model of ICN structure at the k th

level of the hierarchy after the solution of the i th selection problem.

Let a set of modelling steps be determined as:

{}011ik H (H ,H ),H h ,i 1,m,k 1,m ====,

where 0H is the action necessary to change solving the tasks of CIS functioning to solving the tasks of ICN functioning;

ik h is a set of steps for modelling the solution of the i th task at the k th , that represent such series of steps which result in the transition to the (k + 1)th level of the hierarchy of the object structure being modelled.

Then the following relations are correct:

i(k 1)ik ik s ,s(h )s -?????; i(k 1)ik ik h ,h(s )h -?????

,

where ik s(h ) is additional data for the model obtained by

performing step ik h ,

ik h(s ) is the step selected according to the state ik s .

To select step ik h all the states of the model of the complex {}ik s ,i 1,m,k 1,m == should be built. Let the procedure for selecting the step at the k th level

be denoted by k V . Then k

V k k s h ???→, where k s S ∈ is a set of admissible states of the model at the level k . If step k h is not appropriate, the procedure of re-selecting is necessary. This procedure will be denoted by k V *.

Then k V *

k j s h ???→, where j 1,k =, k m ≤. Combining

the expressions obtained, the process of selecting the step can be denoted by the expression:

j j k k j k k

k k V (s ), если V *(s )j,j k h V (s ), если V *(s )k =

Subset S" of the end states of the system model is selected in set S. Then subset S" is split into two more subsets of the second level:

S"(S",S")+-=,

where S"+ is a subset of the end states satisfying CIS safety conditions;

S"- is a subset of the end states that are characterized by a significant level of risk.

The i th selection problem while synthesizing ICN structures factored in the state of the model is denoted as the tuple

i i i Z S ,H ,V,W,i =, i S S"+?, i H H ?, i 1,m =.

In this case, the initial selection problem is defined as:

000Z S ,H ,V,W,0=.

Then the variant synthesis of structures lies in the sequential transition from the solution of problem 0Z to the solution of a certain problem m Z , when the model changes to state m S S"∈. In this case, if m

S

S"+∈, the

execution of the sequence of states 01m S ,S ,..,S is a global task of synthesizing the structures of the target network. Let n Z' be its solution, then the set of all such solutions is:

{}n Z'Z',n 1,m ==

The specified set should be estimated according to the complex criterion of ICN efficiency. Then the formal model of the problem of optimizing the variant synthesis of structures is represented by the tuple

0Z ,Z,Z',F

ψ=,

where F is the complex efficiency criterion.

Let us consider ICN structure at the level of the processes and tasks of applied software (set P). Within model M, the sets of tasks that must be performed by the ith elements will be denoted as

i i i k P p ,k 1,l;i 1,m,P P ===∈.

Let us assume that the execution of each process from

i i

k p P ∈ requires the consumption of information and

computing resource i k M that is subject to optimization

and represented as a hierarchy subordinate to applied processes. To consider repeatedly performed processes, the coefficient i k a is introduced. Then the process i k

p will be executed while consuming information and

computing resources in the amount of i i

k k a M that is subject to optimization.

Pair *j (P ,j)

is called the state of the j th

level, where

*i

j P P P ?? is a subset of the i th

level tasks that can be

performed together without exceeding the level of

magnitude i M . Let i *

j M (P ) be the information and

computational resource consumption in the state with number j. Then

i i i *j j M M (P )0?=-≥

The process of synthesizing the ith level structure consists of changing the sequence of states

***12j i (P ,1),(P ,2),...,(P ,j ), which is carried out in such a

way that the optimization problem according to the local

criterion Fi is solved.

Fig.4. Scheme of the method of determining the parameters of data flows in the context of the fixed information structure of the net

However, it is necessary to take in account a number of external constraints that arise during the execution of the

process i *j j p P ∈, which are denoted by i *

j D (P ). In

particular, vector i *j D (P ) may include resource

component i M . Then the problem of optimal synthesis of the ith level structure factored in external constraints is defined as follows: to find a way to form sets

***

12j

P ,P ,...,P in the model environment ψ, where

i

l i j j 1min, =?→∑i *i j D (P )D ,j=1,l ≤.

The formalization of selecting optimal structure of a multilevel ICN that enables CIS functioning makes construction of corresponding ICN models possible.

After the optimal alternative of the net information structure has been selected, the parameters of data flows should be assigned among its nodes while solving a particular task. These intensities are determined by the intensity of the task execution considering all the users of the net (system). It is believed that each application which is used while executing the task is run once only. The method of determining the parameters of data flows in the context of fixed information structure of the net is shown in Fig.4. The method suggested enables assigning the intensities of data flows to the system nodes. Under these conditions the types of interrelations among the elements of the information structure of thenet and its source data about the amounts of transmitted information are given in Table 1.

Table 1. Parameters of the amounts of transmitted data among the

elements of ICN information structure

IV. C ONCLUSION

To formalize the process of processing information in

CIS the application of the system approach is justified. This approach enabled distinguishing the structural components of selecting structures in ICN environment

and to construct a hierarchical graph of alternative formalization that considers the main relationships that reflect the sequence, amounts and flows of information that is processed among different levels of structures. The construction of this graph is the basis for developing the method for building the optimal structure of ICN.

The means for formal description of ICN information structure were developed; these means definitely determine the parameters of applications and their interrelationship. The basis is the complex mathematical model whose components describe the information structure, data flows and the technical structure of the net. The major parameters of the model of the net information structure which is the basis for developing the models of data flows are described.

The article deals with the following novelty aspects:

- improving the model of the problem of selecting

ICN optimal structure, by means of set-theoretical formalization considering the criterion of the maximum intensity of using the computational resource, which enabled determining the structural links between the basic elements factored in the decomposition of the model to the basic elements "node" and "task";

- developing a new method of building ICN optimal

structure which, unlike the existing ones, assumes the variant synthesis of hierarchy of structures and formalization of selection problems on the basis of set-theoretic models, which makes it possible to ensure the efficient use of information and technical resources of the network.

The formalized model of ICN information structure helped determine the methods of computing a set of parameters and characteristics that describe in particular: the intensities of flows of users’ requests, the intensity of data flows among information nodes, loading to the net nodes, the intensities of flows of request to the databank.

R EFERENCES

[1] Zhenbing Hu, Vadym Mukhin, Yaroslav Kornaga,

Yaroslav Lavrenko, Oksana Herasymenko,"Distributed Computer System Resources Control Mechanism Based on Network-Centric Approach", International Journal of Intelligent Systems and Applications(IJISA), Vol.9, No.7, pp.41-51, 2017. DOI: 10.5815/ijisa.2017.07.05

[2] D. V. Ageev, A. A. Ignatenko, A. N. Kopylev, "Method

for Determination of Flow Parameters in Different Parts of Multiservice Telecommunications Network, Taking Into Account the Effect of Self-Similarity", Electronic scientific specialized edition - journal "Problems of Telecommunications", No. 3 (5), pp. 18-37, 2011. Available at: http://pt.journal.kh.ua/2011/3/1/113_ageyev_ method.pdf (last accessed March 23, 2017).

[3] Yu. Losev, K. Ruccas, "The Comparative Analysis of the

Mathematical Device of Modelling of Telecommunication Networks", Information Processing Systems , Kharkiv: Ivan Kozhedub Kharkiv National Air Force University, No. 8 (66), pp. 55-60, 2007.

[4] Hamed Dinari,"A Survey on Graph Queries Processing:

Techniques and Methods", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.4, pp. 48-56, 2017.DOI:

10.5815/ijcnis.2017.04.06

[5]Ayodeji J. Akande, Colin Fidge, Ernest Foo,"Limitations

of Passively Mapping Logical Network Topologies", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.2, pp.1-11, 2017.DOI: 10.5815/ijcnis.2017.02.01

[6] E. Gelenbe, G. Pujolle, Analysis and Synthesis of

Computer Systems (2nd Edition), Advances in Computer Science and Engineering: Texts. Vol. 4, 309 p., 2010. [7]RFC 1122 –Requirements for Internet Hosts -

Communication Layers. Available at: http://rfc2.ru/1122.rfc (last accessed March 23, 2017). [8]N. S. Marder, Modern Telecommunications, Moscow:

IRIAS, 255 p., 2006.

[9]G. A. Kuchuk, R. P. Gakhov, A. A. Pashnev,

Infocommunication Resources Management, Moscow: Fizmatlit, 220 p., 2006.

[10]I Pepelnjak, EIGRP Network Design Solutions: The

Definitive Resource for EIGRP Design, Deployment and Operation [Теxt], CiscoPress, 384 p., 2000.

[11] C. Paulsen, J. Boyens, Summary of the Workshop on

Information and Communication Technologies Supply Chain Risk Management, National Institute of Standarts and Technology, 21 p., 2012.

[12]G. A. Kuchuk, A. A. Pashnev, "Classification of Control

Tasks for Multi-Service Networks of Distributed Information-Control Systems for Critical Applications", Problems of Management of the Uniform State Civil Protection System: Collection of Materials of the NPC,

4.04.2007, Kharkiv: Ministry of Emergencies, URZU,

pp. 104-106, 2007.

[13]V. G. Olifer, N. A. Olifer, (2012), Computer Networks.

Principles, Technologies, Protocols, (4th Edition), St. Petersburg: Piter, 943 p., 2012.

[14]Zhengbing Hu, Vadym Mukhin, Yaroslav Kornaga,

Yaroslav Lavrenko, Oleg Barabash, Oksana Herasymenko, "Analytical Assessment of Security Level of Distributed and Scalable Computer Systems", International Journal of Intelligent Systems and Applications (IJISA), Vol.8, No.12, pp.57-64, 2016. DOI: 10.5815/ijisa.2016.12.0 [15]V. V. Kosenko, N. G. Kuchuk, "Modeling of Technical

Information and Telecommunication Network Based on its Particular Implementation of Information", Information Processing Systems, Kharkiv: Ivan Kozhedub Kharkiv National Air Force University, No. 9(146), pp. 167-171, 2016.

[16]V. V. Kosenko, N. G. Kuchuk, "Interaction Hardware and

Software While Control Traffic Distribution", Scientific publication "Systems of Arms and Military Equipment",

Kharkiv: Ivan Kozhedub Kharkiv National Air Force University, No. 3(47), pp. 72-75, 2016.

[17]V. V. Kosenko, R. V. Artyukh, A. I. Rogovoi, "Variant

Structure Hierarchy Synthesis Infocommunication Network", Academic Journal "Control, Navigation and Communication Systems",Poltava National Technical Yuri Kondratyuk University, No. 4 (44), pp. 60-63, 2017. Authors’ Profiles

Vadym Mukhin:Professor of

department of mathematical methods

of system analysis of National

Technical University of Ukraine “Kiev

Polytechnic Institute”, Doct. of Sc.

Born on November 1, 1971. M. Sc.

(1994), PhD (1997), Doct. of Sc. (2015)

from the National Technical University

of Ukraine “Kiev Polytechnic Institute”; Assoc. Prof. (2000), Professor (2015).

Major interest: the security of distributed computer systems and risk analysis; design of the information security systems; mechanisms for the adaptive security control in distributed computing systems; the security policy development for the computer systems and networks.

Yury Romanenkov was born in 1977.

He graduated from N. Ye. Zhukovsky

State Aerospace University "Kharkov

Aviation Institute" with a degree in

"Automatic control systems for aircrafts

and complexes". In 2004, he defended

thesis for the degree of Candidate of

technical sciences in the specialty

"Project management and development of production", in 2017 he defended thesis for the degree of Doctor of Technical Sciences in the specialty "Information Technology" in N. Ye. Zhukovsky National Aerospace University "Kharkov Aviation Institute" (Kharkov, Ukraine). From 2000 to the present time he worked as an assistant and an assistant professor; he currently holds a professorship at the Department of Management in N. Ye. Zhukovsky National Aerospace University. "Kharkiv Aviation Institute". He is the author of more than 100 scientific publications. His scientific interests lie in the fields of modelling and forecasting in organizational and technical systems.

Victor Kosenko was born in 1960. He

graduated from Kharkov State

University of Economics and got a

degree in Industrial Management. In

2003 he defended his thesis for the

degree of candidate of technical

sciences, the specialty is "Automated

control systems and innovative

information technologies". From 2006

till 2010 he worked as the deputy director for scientific work at Khark?v Scientific and Research Institute of Mechanical Engineering Technology, since 2010 he has held the post of the director of Khark?v Scientific and Research Institute of Mechanical Engineering Technology. He is the author of more than one hundred scientific publications. He is a corresponding member of the Engineering Academy of Sciences of Ukraine. His scientific interests lie in the field

of management systems and information technologies.

Anton Rohovyi was born in 1973. He

graduated from Kharkov State

Polytechnic University with a degree in

Computerized Information Processing

and Control Systems. In 2000, he

defended his thesis for the degree of

candidate of technical sciences on the

specialty "Automated control systems and

advanced information technologies" in National Technical

University "Kharkiv Polytechnic Institute" (Kharkiv, Ukraine).

From 2000 to the present time he worked as an assistant and

currently works as an associate professor at the Strategic

Management Department of National Technical University

"Kharkiv Polytechnic Institute". He is the author of more than

30 scientific publications. Scientific interests - project

management, modeling of complex systems development, big

data.

Anna Kharazii was born in 1984. She

graduated from National Technical

University "Kharkiv Polytechnic Institute",

specializing in Project Management. In

2016 she defended her thesis for the

degree of candidate of technical sciences

on the specialty "Management of Projects

and Programs" in O.M.Beketov National

University of Urban Economy (Kharkiv,

Ukraine).

From 2007 to the present time she worked as a technician,

engineer, senior engineer and currently works as an assistant at

the Strategic Management Department National Technical

University "Kharkiv Polytechnic Institute".

She has 13 scientific publications. Scientific interests - IT

project management, IT project management methodology,

analysis of big data.

Julia Bilokin was born in 1984. She

pursued her Master’s degree in Safety

Management at National Aerospace

University “Kharkiv Aviation Institute”,

Kharkiv, Ukraine in 2007. She obtained

the Ph. D. degree in Project and Program

Management from National Aerospace

University “Kharkiv Aviation Institute”

in 2011. She is currently working as

Associate Professor at the Department of Information Control

Systems, National Aerospace University “Kharkiv Aviation

Insti tute”. She has published various research papers in

international and national journals and conferences. Her

research interest focuses on Project and Program Management,

Life Cycle Management and Structural Analysis.

Natalia Kosenko was born in 1981. She

graduated from N. Ye. Zhukovsky

National Aerospace University "Kharkov

Aviation Institute" and got a degree in

"Project Management". In 2015 she

defended her thesis for the degree of

Candidate of Technical Sciences in

specialty "Project and Program

Management".

From 2009 to 2014 she worked as an assistant at the

Department of Management of N. Ye. Zhukovsky National

Aerospace University "Kharkiv Aviation Institute". From 2014

to 2015 she occupied a position of Junior Researcher of the

Department of Technology and Automation of Production of

Radioelectronic and Electronic Computing Means in Kharkov

National University of Radio Electronics. Since 2015 she has

been working as Associate Professor at the Department of

Project Management in the Urban Economy and Construction in

A. N. Beketov Kharkiv National University of Municipal

Economy. She is the author of more than thirty scientific

publications. Her scientific interests lie in the sphere of project

and program management as well as in the management of

project human resources.

Su Jun: PhD, Associate Professor of

School of Computer Science, Hubei

University of Technology. He received

Ph.D. degree in Computer Systems and

Components from Ternopil National

Economic University, Ternopil, Ukraine

in 2013. He has published more than ten

papers in the area of Computer Network

and wireless communication. His

research interests include Wireless Sensor Network, Self-

organizing network technology, Wave propagation and

electromagnetic interference. Dr. Su is a member of IEEE and

ACM.

How to cite this paper: Vadym Mukhin, Yury Romanenkov,

Julia Bilokin, Anton Rohovyi, Anna Kharazii, Viktor Kosenko,

Nataliia Kosenko, Jun Su, "The Method of Variant Synthesis of

Information and Communication Network Structures on the

Basis of the Graph and Set-Theoretical Models", International

Journal of Intelligent Systems and Applications(IJISA), Vol.9,

No.11, pp.42-51, 2017. DOI: 10.5815/ijisa.2017.11.06

图与网络模型及方法学习心得

图与网络模型及方法学习心得 摘要：图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的《哥尼斯堡的七座桥》。1847年，克西霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计算烷烃的同分异构体时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈。近几十年来，计算机技术和科学的飞速发展，大大促进了凸轮的研究和应用，凸轮的理论和方法已经渗透到物理、化学、通信科学、建筑学、运筹学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点来表示这些具体的事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”、七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 正文：在寒假中，学习了图论这一章以后，对于此类问题的解决方法就是构造

图论 模型

251 图论模型 图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。 图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（D. K?nig ）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。 9.1 图的基础理论 9.1.1 图的基本概念 所谓图，概括地讲就是由一些点和这些点之间的连线组成的。定义为(,)G V E =，V 是顶点的非空有限集合，称为顶点集。E 是边的集合，称为边集。边一般用(,)i j v v 表示，其中 ,i j v v 属于顶点集V 。 以下用V 表示图(,)G V E =中顶点的个数，E 表示边的条数。 如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为 (,)G V E =，123{,,}V v v v =，1213{(,),(,)}E v v v v =. 2 3 v 45 v 3 4 (a) (c) 图9.1 图的示意图 1.无向图和有向图 如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。如图9.1 (a)和(b)都是无向图。连接两顶点i v 和j v 的无向边记为(,)i j v v 或(,)j i v v 。 如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。连接两顶点i v 和j v 的弧记为,i j v v ??，其中i v 称为起点，j v 称为终点。显然此时弧,i j v v ??与弧,j i v v ??是不同的两条有向边。有向图的弧的起点称为弧头，弧的终点称为弧尾。有向图一般记为(,)D V A =，其中V 为顶点集，A 为弧集。 例如图9.1 (C)可以表示为(,)D V A =，顶点集1234{,,,}V v v v v =，弧集为1223{,,,, A v v v v =????243441,,,,,}v v v v v v ??????。 对于图除非指明是有向图，一般地，所谓的图都是指无向图。有向图也可以用G 表示。 例9.1 设12345{,,,,}V v v v v v =，12345{,,,,}E e e e e e =，其中

复杂网络基础2(M.Chang)

复杂网络基础理论 第二章网络拓扑结构与静态特征

第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2

2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3

2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录

2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5

2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6

数学建模 图与网络模型及方法

第五章 图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。１847年，克希霍夫为了给出电网络方程而引进了“树”的概念。１857年,凯莱在计数烷22 n n H C 的同分异构物时,也发现了“树”.哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用,图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图"是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功.欧拉为了解决 这个问题，采用了建立数学模型的方法.他将每一块陆地用一个点来代替,将每一座桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”.问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点,给出了一笔画的一个判定法则:这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题,而且开创了图论研究的先河. 图与网络是运筹学(Operat ｉons Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域.下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题. 我们首先通过一些例子来了解网络优化问题. 例1 最短路问题（ＳPP －shorte ｓｔ pat ｈ p ｒｏb ｌｅm ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路，使得总

图论基础知识

图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。 图的基本概念 图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→

y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。 图2.1：网络拓扑结构示意图。图a 是10阶有向图，顶点集为 {1,2,3,4,5,6,7,8,9,10}，边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b 是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如

信息技术-信息技术网络分析与网络计划 62页 精品

第六章网络分析与网络计划 网络分析是图论的一个应用分支．它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题．在现实生活和生产实践中，网络分析方法有很广泛的应用．如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等．由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段． 网络计划方法是上世纪50年代发展起来的计划控制技术，主要包括计划评审技术(programme evaluation and review technique，简称PERT)和关键路径方法(critical path method或critical path analysis，简称CPM、CPA)．网络计划方法特别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的重要应用分支． 本章在引入有关图的一些基本概念的基础上，介绍最小生成树、网络最短路、最大流、最小费用最大流等网络分析模型及其解法；并对网络计划图（统筹图）的制作、作业时间参数计算、关键线路方法和计划评审技术等网络计划基本技术和方法进行初步介绍． 第一节图的基本概念 一、图 现实世界中有许多具体事物及关系可以用图形来抽象表示．例如，路线关系、工序安排、区位规划等都可以用图来表达． 我们先通过几个直观的例子，来认识什么是图． 例6-1 歌尼斯堡七桥问题 哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系，由新河、旧河及其交汇 而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地之间有七座桥连通，如图6-1(a)所示．当时城内居民在散步时热衷于这样一个问题：从某陆

第五篇图论网络建模习题答案

第十六章习题 1. 某城市要建立一个消防站，为该市所属的七个区服务，如图16-13所示，问应设在哪个区，才能使它至最远区的路径最短。 1 v 2 v 3 v 4 v 5 6 7 1.5 4 图16-13 解：本题首先需要求出任意两点间的最短路，然后判断选择在哪个区建立消防站解： (1)求任意两点间的最短路，matlab 程序如下 clear; clc; M=10000; a(1,:)=[0,3,M,M,M,M,M]; a(2,:)=[zeros(1,2),2,M,1.8,2.5,M,]; a(3,:)=[zeros(1,3),6,2,M,M]; a(4,:)=[zeros(1,4),3,M,M]; a(5,:)=[zeros(1,5),4,M]; a(6,:)=[zeros(1,6),1.5]; a(7,:)=zeros(1,7); b=a+a';path=zeros(length(b)); for k=1:7 for i=1:7 for j=1:7 if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end end end b, path 得任意两点间距离矩阵（列表）：

(2) 计算在点i v 设立服务设施时的最大服务距离，即i v 到各点距离的最大值（见表中最后一列）； (3) 第二个区距离最远的区路径最短，为4.8，所以应该选择第二个区建立消防站。 2．对图16-14，求最小生成树。 图16-14 解：最小生成树matlab 程序如下 clc;clear; a(1,:)=[0,56,35,2,51,60]; a(2,:)=[zeros(1,2),21,57,78,70]; a(3,:)=[zeros(1,3),36,68,68]; a(4,:)=[zeros(1,4),51,61]; a(5,:)=[zeros(1,5),13]; a(6,:)=zeros(1,6); a=a+a'; result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1));

图论基础知识汇总(适合建模)

图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两

§2-1网络图论的基本概念

§2-1 网络图论的基本概念 对于一个电路图，如果用点表示其节点，用线段表示其支路，得到一个由点和线段组成的图，这个图被称为对应电路图的拓扑图，通常用符号G 表示。例如：图2-1-1（a ）所示电路，其对应的拓扑图如图2-1-1 (b) 所示。 拓扑图是线段和点组成的集合，它反映了对应的电路图中的支路数、节点数以及各支路与节点之间相互连接的信息。 在拓扑图中，如果任意两点之间至少有一条连通的途径，那么这样的图称为连通图，例如图2-1-1（b ）所示的图，否则称为非连通图，例如图2-1-2（b ）所示的图。如果图G 1中所有的线段与点均是图G 中的全部或部分线段与点，且线段与点的连接关系与图G 中的一致，那么图G 1称为图G 的子图。例如图2-1-3（b ）（c ）（d ）（e ）均是图2-1-3（a ）的子图。 图 2-1-1 图2-1-2 图2-1-3

下面介绍网络图论中非常重要的一个概念——树。树是连通图G 的一个特殊子图，必须同时满足以下三个条件： （1）子图本身是连通的； （2）包括连通图G 所有节点； （3）不包含任意回路。 组成树的支路称为树支，不包含在树上的支路称为连支（或链支）。如果用t n 表示树支的数目，则： 1t n n =- （式2-1-1） 连支的数目l 等于支路数b 减去树支的数目，即 1l b n =-+ （式2-1-2） 如果将一个电路铺在一个平面上，除节点之外再没有其他交点，这样的电路被称为平面电路，否则，称为非平面电路。 在平面电路中，内部没有任何支路的回路称为网孔。它是一种特殊的回路。 一个有b 条支路、n 个节点的连通平面图的网孔数m 为： 1m b n =-+ （式2-1-3） 接下来介绍割集的概念。割集是连通图G 的一个子图，它满足以下两个条件： （1）移去该子图的全部支路，连通图G 将被分为两个独立部分； （2）当少移去该子图中任一条支路时，则图仍然保持连通。 一个具有n 个节点的连通图，有（n-1）条树，有（n-1）个单树支割集。 (a) (b) 图2-1-7

2021年数学建模- 图与网络模型及方法

第五章 图与网络模型及方法 欧阳光明（2021.03.07） §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分 异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当

然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2公路连接问题

脑网络研究中的图论指标详解_69

人脑是自然界中最复杂的系统之一, 在复杂系统研究方面，网络研究的方法在21世纪以来被深度应用在多个领域； 在神经科学研究领域中，无论从微观的多个神经元、神经元集群的角度看还是从宏观的多个脑区相互连接成庞杂的结构网络和通过相互作用构建的功能网络看，网络方法都已经延伸到了神经科学研究中的方方面面。 在网络研究中，通过图论方法来表征复杂网络的拓扑关系是研究网络中不同节点、不同连边以及网络的整体特性的重要手段。 但在实际的研究中，研究者往往根据自己的研究目的特定地选择网络属性，因而导致很多研究人员无法全面的了解图论研究中多种指标的实际含义； 同时，随着图论方法的发展，许多新的指标也不断出现。全面和准确的理解图论指标对于使用图论方法研究复杂网络具有重要的意义，只有选对指标才能更好地说明你的研究问题，达到事半功倍的效果。 因此，思影科技汇总了当前网络研究中被研究者经常使用的图论指标，并结合图表示、数学公式的严格定义以及解析的方法对每个指标进行了详述，以更好的帮助各位希望使用网络方法和图论指标进行脑科学研究的研究者。 首先我们来简单的回顾下网络中的不同对象，以便在后文阅读中能够清楚不同术语所描述的网络对象。 下图是一个由11个节点组成的网络，即圆圈，它们表示了网络中的基本对象，连接不同的节点的连线被称为“边”； 在脑网络研究中，节点是被按照不同分割依据所分割的脑区，连边在功能网络中往往通过对不同脑区的时间序列信号的相关计算所得，而结构网络中分为DTI连接和基于灰质变化的协变网络连边。 在这个小的网络中，我们可以看到不同节点由数量不等的连边互相连接起来，为了能够全面的分析这个网络的拓扑结构，我们需要使用不同的图论指标。 接下来我们来一起了解不同的网络指标。 （1）度（node degree） 在网络研究中，最基本和最广泛使用的度量指标是“度”，对于给定节点，度就是与它连接的邻居个数。第i个节点的度计算公式是： 这里，Cij表示节点i和节点j之间的连接状态，当节点i和节点j之间有连接时，Cij=1,当节点i和节点j之间无连接时，Cij=0；