BellmanFordShortestPath<V,E>	Класс, реализующий алгоритм Беллмана-Форда.
BiconnectivityInspector<V,E>	Класс, предназначенный для проверки графа на двусвязность.
BlockCutpointGraph<V,E>	Класс, являющийся двумя сущностями: «блок» и «точка сочленения»ю
BronKerboschCliqueFinder<V,E>	Класс, содержащий реализацию алгоритма Брона-Кербоша поиска клик в графе.
ChromaticNumber	Класс для приближенного поиска хроматического числа графа.
ConnectivityInspector<V,E>	Класс, работающий с сущностью «связный граф».Обеспечивается проверка на связность, поиск вершин и ребер по определенным условиям и многое другое.
CycleDetector<V,E>	Класс, реализующий поиск циклов в графе.
DijkstraShortestPath<V,E>	Класс, содержащий реализацию алгоритма Дейкстры для поиска кратчайшего пути между вершинами.
DirectedNeighborIndex<V,E>	Класс, предназначенный для поиска окружения произвольной вершины в графе.
EdmondsKarpMaximumFlow<V,E>	Класс, реализующий сущность «поток в сети».
EulerianCircuit	Класс, содержащий алгоритм поиска эйлерова пути.
FloydWarshallShortestPaths<V,E>	Класс, реализующий алгоритм Флойда для поиска кратчайших путей между всеми вершинами графа.
HamiltonianCycle	Класс, содержащий реализацию алгоритма поиска гамильтонова пути в графе.
VertexCovers	Класс, содержащий реализацию алгоритма поиска вершинного покрытия в графе.

Из рассмотренного примера видно, насколько большой функционал у библиотеки JGraphT и насколько сильно он облегчает работу алгоритмиста.

Документация по JGraphT содержится по адресу: http://www.jgrapht.org/javadoc.

Глава 6. Обзор библиотеки JGraph.

Что же касается библиотеки JGraph, то она в свою очередь:

1) является swing-компонентом для построения графического интерфейса пользователя;

2) содержит более сложное API, чем JGraphT, и поэтому для ее правильного и эффективного использования необходимо изучить предоставляемую документацию;

3) производительность кода, написанного с использованием JGraph, является менее быстрой, чем JGraphT, и поэтому эта библиотека более требовательна к ресурсам.

Следующий адрес http://jgrapht.sourceforge.net/visualizations.html содержит пример работы библиотеки JGraph.

Рисунок 1.

На рисунке 1 мы видим граф на четырех вершинах v1, v2, v3, v4, содержащий ребра v1v2, v2v3, v3v1, v4v3. Этот написанный на языке Java апплет поддерживает пользовательский интерфейс типа drag and drop, благодаря чему пользователь может упорядочить вершины графа по своему усмотрению:

Рисунок 2

Ниже приведен исходный код рассмотренной выше программы на языке Java.

package org.jgrapht.demo;

import java.awt.Color;

import java.awt.Dimension;

import java.awt.Rectangle;

import java.util.HashMap;

import java.util.Map;

import javax.swing.JApplet;

import javax.swing.JFrame;

import org.jgraph.JGraph;

import org.jgraph.graph.DefaultGraphCell;

import org.jgraph.graph.GraphConstants;

import org.jgrapht.ListenableGraph;

import org.jgrapht.ext.JGraphModelAdapter;

import org.jgrapht.graph.ListenableDirectedGraph;

import org.jgrapht.graph.DefaultEdge;

public class JGraphAdapterDemo extends JApplet {

private static final Color DEFAULT_BG_COLOR =

Color.decode( "#FAFBFF" );

private static final Dimension DEFAULT_SIZE = new Dimension( 530, 320 );

private JGraphModelAdapter m_jgAdapter;

/**

* @see java.applet.Applet#init().

public void init( ) {

// create a JGraphT graph

ListenableGraph g = new ListenableDirectedGraph( DefaultEdge.class );

// create a visualization using JGraph, via an adapter

m_jgAdapter = new JGraphModelAdapter( g );

JGraph jgraph = new JGraph( m_jgAdapter );

adjustDisplaySettings( jgraph );

getContentPane( ).add( jgraph );

resize( DEFAULT_SIZE );

// add some sample data (graph manipulated via JGraphT)

g.addVertex( "v1" );

g.addVertex( "v2" );

g.addVertex( "v3" );

g.addVertex( "v4" );

g.addEdge( "v1", "v2" );

g.addEdge( "v2", "v3" );

g.addEdge( "v3", "v1" );

g.addEdge( "v4", "v3" );

// position vertices nicely within JGraph component

positionVertexAt( "v1", 130, 40 );

positionVertexAt( "v2", 60, 200 );

positionVertexAt( "v3", 310, 230 );

positionVertexAt( "v4", 380, 70 );

// that's all there is to it!...

}

private void adjustDisplaySettings( JGraph jg ) {

jg.setPreferredSize( DEFAULT_SIZE );

Color c = DEFAULT_BG_COLOR;

String colorStr = null;

try {

colorStr = getParameter( "bgcolor" );

}

catch( Exception e ) {}

if( colorStr != null ) {

c = Color.decode( colorStr );

}

jg.setBackground( c );

}

private void positionVertexAt( Object vertex, int x, int y ) {

DefaultGraphCell cell = m_jgAdapter.getVertexCell( vertex );

Map attr = cell.getAttributes( );

Rectangle b = GraphConstants.getBounds( attr );

GraphConstants.setBounds( attr, new Rectangle( x, y, b.width, b.height ) );

Map cellAttr = new HashMap( );

cellAttr.put( cell, attr );

m_jgAdapter.edit( cellAttr );

}

Заключение

Из всего выше сказанного следует, что «информационный бум» оставил свой след во многих сферах человеческой жизни. С появлением компьютерных технологий стало возможно решать такие математические задачи, за которые раньше учёные не могли даже взяться именно из-за большой вычислительной сложности таких задач. Да что и говорить, само бурное развитие теории графов во многом обязано именно появлению вычислительных машин. И наоборот, во многом благодаря теории графов стал возможен такой большой скачок в их производительности.

Как известно, немаловажным понятием теории графов является понятие алгоритма. Практическое применение алгоритмов связано именно с использованием ЭВМ.

Основной целью этой работы являлось применение информационных технологий в теории графов. И это применение, поистине, безгранично. Начиная с текстовых редакторов, редакторов изображений и заканчивая огромным количеством всевозможных библиотек в языках программирования.

Список литературы к реферату

1. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – М.; Наука, 1990. 384 c.

2. Перез-Чернов А.Х., Тышкевич Р.И. К проблеме распознавания реберных графов линейных 3-униформных гиперграфов: предбольшие клики // Труды института математики. 2007. Т.15. № 2. С 78-89.

3. Скумс П.В, Суздаль С.В., Тышкевич Р.И. О пороге полиномиальной разрешимости для задачи распознавания графов пересечений ребер линейных 3-униформных гиперграфов // Докл. НАН Беларуси. 2004. Т.48. № 4. С.29-34.

Предметный указатель к реферату

«Лемма о рукопожатиях», 4

Adobe Photoshop, 9

Corel Draw, 9

Internet, 14, 18

JGraph, 9, 10, 11, 12, 13

JGraphT, 9, 10, 11, 12, 13

Microsoft PowerPoint, 9

Microsoft Visio, 9

Microsoft Word, 9

NP-полная задача, 8

NP-трудная задача, 8

O-символика, 7

TeX, 9

абстрактная вычислительная машина, 5

вход задачи, 6

граф взвешенный, 5, 6

длина списка, 5

задача «k-раскраска», 8

задача «О Кёнигсбергских мостах», 4

задача 3-раскраска, 8

линейный алгоритм, 7

матрица весов, 5

матрица смежности, 5, 6

ориентированный граф, 6, 19

полиномиальная сложность, 8

полиномиальный алгоритм, 7

последовательное представление списка, 5

сложность, 7, 8

список, 5

список ребер, 6

список смежности, 6

трудоемкость, 7

ЭВМ, 4, 5, 6

элементарная операция, 5

Интернет ресурсы в предметной области исследования

1. http://www.jgraph.com – официальный сайт проекта JGraph.

2. http://arxiv.org – сервис для поиска статей по математике, компьютерным наукам, физике, биологии, статистике.

3. http://poiskknig.ru - поисковая машина электронных книг, свободно распространяемых в интернете. Главным приоритетом является образовательная литература, являющаяся базисом научного и технического знания.

4. http://lib.org.by – библиотека научной литературы по математике, компьютерным наукам, физике, инженерным наукам.

5. http://exponenta.ru – образовательный сайт по математике.

6. http://www.vak.org.by/ – сайт Высшей аттестационной комиссии Республики Беларусь.

Действующий личный сайт в WWW

Ссылка на мой личный сайт в сети Internet:

http://raman-piatrovich.narod.ru.

Граф научных интересов.

магистранта Петровича Р.А.

Механико-математический факультет.

Специальность: 01.01.09 – дискретная математика и математическая кибернетика

Смежные специальности

01.01.02 – дифференциальные уравнения

1. Развитие теории обыкновенных дифференциальных уравнений и уравнений в частных производных, интегральных, интегро-дифференциальных, функционально-дифференциальных, дифференциально-операторных уравнений и дифференциальных уравнений со случайными параметрами.

2. Обоснование численных методов решения дифференциальных, интегральных, интегро-дифференциальных, функционально-дифференциальных и дифференциально-операторных уравнений.

3. Разработка методов дифференциальных уравнений для решения задач механики, математической физики и других прикладных наук.

01.01.05 – теория вероятностей и математическая статистика

1. Вероятностные пространства и случайные элементы.

2. Предельные теоремы.

3. Случайные процессы и поля.

4. Стохастический анализ и стохастические дифференциальные уравнения.

5. Случайные процессы специального вида, включая процессы массового обслуживания.

6. Статистические выводы и анализ данных.

7. Последовательный анализ.

8. Непараметрическая и робастная статистика.

9. Статистика случайных процессов, полей и временных рядов.

10. Вероятностно-статистическое моделирование.

01.01.07 – вычислительная математика

1. Теория приближенных методов и численных алгоритмов решения задач алгебры, дифференциальных и интегральных уравнений, задач дискретной математики, экстремальных задач, задач управления, некорректных задач других задач линейного, нелинейного и стохастического анализа.

2. Теория и методы параллельных вычислений.

3. Численные методы и алгоритмы решения прикладных задач, возникающих при математическом моделировании естественнонаучных, научно-технических, социальных и других проблем.

Основная специальность

«Применение информационный технологий в теории графов» (стр. 3 из 5)